Problem:


Score : 400 points

Problem Statement

Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.

In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.

Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t.

Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq s,t \leq n

s \neq t

1 \leq u_i < v_i \leq n

1 \leq a_i,b_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

Any city can be reached from any city by changing trains.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m s t
u_1 v_1 a_1 b_1
:
u_m v_m a_m b_m

Output

Print n lines.
In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.

Sample Input 1

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

Sample Output 1

999999999999998
999999999999989
999999999999979
999999999999897

After 0 years, it is optimal to do the exchange in City 1.

After 1 years, it is optimal to do the exchange in City 2.

Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed.

After 2 years, it is optimal to do the exchange in City 3.

After 3 years, it is optimal to do the exchange in City 4.
Note that the same train can be used multiple times.

Sample Input 2

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

Sample Output 2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994



Sample input:
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1


Sample output:
999999999999998
999999999999989
999999999999979
999999999999897

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=[]
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.append(MIN)

  print(*[10**15-ans[-i-1] for i in range(n)])
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
n,m,s,t = map(int, input().split())
uvab=[list(map(int,input().split())) for i in range(m)]

from heapq import heappush, heappop,heappushpop,heapify
def dks(g,start,num_v):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))
    cost = [INF] * num_v
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

link_yen = [[] for _ in range(n)]
link_snk = [[] for _ in range(n)]
for u,v,a,b in uvab:
    link_yen[u-1].append([v-1,a])
    link_yen[v-1].append([u-1,a])
    link_snk[u-1].append([v-1,b])
    link_snk[v-1].append([u-1,b])

cost_yen = dks(link_yen,s-1,n)
cost_snk = dks(link_snk,t-1,n)

ans=[]
mn=float("inf")
for i in reversed(range(n)):
    new_cost = cost_yen[i] + cost_snk[i]
    mn=min(mn,new_cost)
    ans.append(mn)

for a in reversed(ans):
    print(10**15 - a)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

n,m,s,t=map(int,input().split())
INF=10**20
G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  G1[u-1][v-1] = G1[v-1][u-1] = a
  G2[u-1][v-1] = G2[v-1][u-1] = b
  
def dijkstra(G,start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    que = []
    heappush(que, (0, start))

    while len(que):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d
  
d1 = dijkstra(G1,s-1)
d2 = dijkstra(G2,t-1)

ans=[]
MIN = INF
for i in range(n-1,-1,-1):
  MIN = min(MIN,d1[i]+d2[i])
  if i == s-1:
    MIN = min(MIN,d2[s-1])
  if i == t-1:
    MIN = min(MIN,d1[t-1])
    
  ans.append(MIN)
  
print(*[10**15-ans[-i-1] for i in range(n)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
UVAB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for u,v,a,b in UVAB:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))

import heapq
INF = float('inf')
costy = [INF] * N
costy[S] = 0
hq = [(0,S)]
while hq:
    c,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if costy[to] <= c+a: continue
        costy[to] = c+a
        heapq.heappush(hq, (c+a,to))

costs = [INF] * N
costs[T] = 0
hq = [(0,T)]
while hq:
    c,v = heapq.heappop(hq)
    for to,_,b in es[v]:
        if costs[to] <= c+b: continue
        costs[to] = c+b
        heapq.heappush(hq, (c+b,to))

ans = [0]
for y,s in reversed(list(zip(costy,costs))):
    ans.append(max(ans[-1], 10**15 - y - s))

print(*ans[1:][::-1], sep='\n')

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra_heap(v, start, edge):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


def resolve():
    init = 10 ** 15
    n, m, s, t = map(int, input().split())
    edge_en = [[] for _ in range(n)]
    edge_sn = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        edge_en[u - 1].append([a, v - 1])
        edge_en[v - 1].append([a, u - 1])
        edge_sn[u - 1].append([b, v - 1])
        edge_sn[v - 1].append([b, u - 1])

    cost_en = dijkstra_heap(n, s - 1, edge_en)
    cost_sn = dijkstra_heap(n, t - 1, edge_sn)
    costs = []
    for i in range(n):
        total_cost = cost_en[i] + cost_sn[i]
        costs.append([total_cost, i])

    heapify(costs)
    cost = 0
    now = -1
    for i in range(n):
        while costs and now < i:
            if costs[0][1] < i:
                heappop(costs)
            else:
                cost, now = heappop(costs)
                break
        print(init - cost)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 15
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    MONEY_MAX = 10 ** 15
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    city_cost = [(cost, city) for city, cost in enumerate(min_cost)]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = MONEY_MAX - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq
#n:頂点数、m:辺の数　s:始点　es:辺のリスト
def dijkstra(n,m,s,es):
  #used:訪問済みかどうかを確認する　false 使ってない
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**18
    d = [INF] * n
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


n,m,s,t = map(int, input().split())
gal = [ [] for _ in range(n+1) ]
gbl = [ [] for _ in range(n+1) ]

for _ in range(m):
    u,v,a,b = map(int, input().split())
    gal[u].append((v,a))
    gal[v].append((u,a))
    gbl[u].append((v,b))
    gbl[v].append((u,b))

adl = dijkstra(s,n+1,gal)
bdl = dijkstra(t,n+1,gbl)
ansl = [0]*n
curr_min = 10**18

# print(adl)
for i in range(n-1,-1,-1):
    cost = adl[i+1] + bdl[i+1]
    curr_min = min(cost, curr_min)
    ansl[i] = 10**15-curr_min
    # print('--',i)
    # print(cost)

for ans in ansl:
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush as pu, heappop as po

n,m,s,t = map(int,input().split())
e = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    e[u].append((v,a,b))
    e[v].append((u,a,b))

def dik(s,v):
    S = [float("INF")]*(n)
    S[s] = 0
    h = []
    pu(h,[0,s])
    while h:
        d,now = po(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                pu(h,[d+b,a])
    return S[::-1]
ans = []
cost = 10**15
now = 0
for i,j in zip(dik(s-1,1),dik(t-1,2)):
    now = max(now,cost-i-j)
    ans.append(now)
print(*ans[::-1],sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush as pu, heappop as po

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))

def dik(s,v):
    S = [float("INF")]*(n+1)
    S[s] = 0
    h = []
    pu(h,[0,s])
    while h:
        d,now = po(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                pu(h,[d+b,a])
    return S[::-1]
ans = []
cost = 10**15
now = 0
for i,j in zip(dik(s,1),dik(t,2)):
    now = max(now,cost-i-j)
    ans.append(now)
print(*ans[:-1][::-1],sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))
    
def dik(s,v):
    S = [float("INF")]*(n+1)
    S[s] = 0
    h = []
    heappush(h,[0,s])
    while h:
        d,now = heappop(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                heappush(h,[d+b,a])
    return S
S = dik(s,1)
T = dik(t,2)
ans = [0]*(n)
cost = 10**15
now = 0
for i in range(n-1,-1,-1):
    now = max(now,cost-S[i+1]-T[i+1])
    ans[i] = now
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))

S = [float("INF")]*(n+1)
S[s] = 0
h = []
heappush(h,[0,s])
while h:
    d,now = heappop(h)
    for nex,a,b in e[now]:
        if d+a < S[nex]:
            S[nex] = d+a
            heappush(h,[d+a,nex])
T = [float("INF")]*(n+1)
T[t] = 0
h = []
heappush(h,[0,t])
while h:
    d,now = heappop(h)
    for nex,a,b in e[now]:
        if d+b < T[nex]:
            T[nex] = d+b
            heappush(h,[d+b,nex])

ans = [0]*(n+1)
cost = 10**15
now = 0
for i in range(n,0,-1):
    now = max(now,cost-S[i]-T[i])
    ans[i] = now
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))
S = [float("INF")]*(n+1)
S[s] = 0
q = deque([])
q.append([s,-1])
while q:
    now,bef = q.popleft()
    for nex,a,b in e[now]:
        if nex == bef:
            continue
        if S[now]+a < S[nex]:
            S[nex] = S[now]+a
            q.append([nex,now])
T = [float("INF")]*(n+1)
T[t] = 0
q = deque([])
q.append([t,-1])
while q:
    now,bef = q.popleft()
    for nex,a,b in e[now]:
        if nex == bef:
            continue
        if T[now]+b < T[nex]:
            T[nex] = T[now]+b
            q.append([nex,now])

ans = [0]*(n+1)
cost = 10**15
now = 0
for i in range(n,0,-1):
    now = max(now,cost-S[i]-T[i])
    ans[i] = now
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
import sys
import heapq
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
#######ここから天ぷら########
n,m,s,t=map(int,input().split())
s-=1;t-=1
def dijkstra(s,G):
    dist=[inf for i in range(n)] #sからの距離のリスト
    dist[s]=0
    mirai=[True for i in range(n)] #Trueなら未確定
    mirai[s]=False

    queue=[] #こいつがheapqになる
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  #重みと行先を1つの変数で表してる！
    while queue:
        minedge= heapq.heappop(queue)
        #miraiがTrueのやつ(未確定なやつ)から最小距離のものをさがす
        if not mirai[minedge%(10**6)]: continue
        #距離が小さいものから"確定"していく
        v=minedge%(10**6) #最小距離の頂点
        dist[v] = minedge//(10**6) #その距離
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                #queueに入る数は、必ず「sからの」距離と行先を持っている
    return dist

G1= [[] for i in range(n)]
G2= [[] for i in range(n)]
for  i in range(m):
    a,b,y,p=map(int,input().split())
    a-=1;b-=1
    G1[a].append((y,b))
    G1[b].append((y,a))
    G2[a].append((p,b))
    G2[b].append((p,a))
A=dijkstra(s,G1)
B=dijkstra(t,G2)
C=[i+j for i,j in zip(A,B)]
ANS=[0]*(n) ; ANS[-1]=C[-1]
for i in range(n-2,-1,-1):
    ANS[i]= min(ANS[i+1], C[i])
for i in range(n):
    print(10**15-ANS[i])

Submission status: Accepted

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

def main():
  n, m, s, t = map(int, input().split())
  
  inf = pow(10, 15)
  
  tree = [[] for _ in range(n)]
  for i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u-1].append((v-1, a, b))
    tree[v-1].append((u-1, a, b))
  
  ans_yen = [0]*n
  ans_snuke = [0]*n
  
  for start, ans in zip([s-1, t-1], [ans_yen, ans_snuke]):
    already = [False]*n
    not_yet = [(0, start)]
    
    while len(not_yet) > 0:
      c, p = heappop(not_yet)
      if already[p]:
        continue
      ans[p] = c
      already[p] = True
      
      for (value, a, b) in tree[p]:
        if already[value]:
          continue
        if start == s-1:
          cost = a
        else:
          cost = b
        heappush(not_yet, (c+cost, value))
  
  ans = [0]*n
  sub = inf
  for i in range(n-1, -1, -1):
    sub = min(sub, ans_yen[i]+ans_snuke[i])
    ans[i] = sub
  
  sub = inf
  for a in ans:
    print(sub-a)
      
  
  
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for i in range(m)]

def dijkstra(s,e):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e1 = [[] for _ in range(n)]
e2 = [[] for _ in range(n)]
for i in range(m):
    a,b,en,su = uvab[i]
    a,b = a-1, b-1
    e1[a].append((en, b))
    e1[b].append((en, a))
    e2[a].append((su, b))
    e2[b].append((su, a))

c1=dijkstra(s-1,e1)
c2=dijkstra(t-1,e2)
# print(c1)
# print(c2)
hlst=[]
for i in range(n):
    hlst.append((c1[i]+c2[i],i))
# print(hlst)
heapq.heapify(hlst)
# print(hlst)
for i in range(n):
    while hlst[0][1]<i:
        heapq.heappop(hlst)
    print(10**15-hlst[0][0])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict
    INF = float('INF')

    n, m, s, t = map(int, readline().split())

    edge = defaultdict(list)

    for _ in range(m):
        u, v, a, b = map(int, readline().split())
        edge[u].append((v, a, b))
        edge[v].append((u, a, b))

    dist_s = defaultdict(lambda: float("INF"))
    dist_t = defaultdict(lambda: float("INF"))

    dist_s[s] = 0
    dist_t[t] = 0

    hq = []
    heapq.heappush(hq, (0, s))

    while hq:
        cost, cur = heapq.heappop(hq)
        for nx, a, _ in edge[cur]:
            nc = cost + a
            if nc < dist_s[nx]:
                dist_s[nx] = nc
                heapq.heappush(hq, (nc, nx))

    heapq.heappush(hq, (0, t))

    while hq:
        cost, cur = heapq.heappop(hq)
        for nx, _, b in edge[cur]:
            nc = cost + b
            if nc < dist_t[nx]:
                dist_t[nx] = nc
                heapq.heappush(hq, (nc, nx))

    res = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        res[i] = max(res[i + 1], 10 ** 15 - (dist_s[i + 1] + dist_t[i + 1]))

    for i in range(n):
        print(res[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def dijkstra(G, s=0):
    n = len(G)
    que = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in G[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist

n, m, s, t = LI()
s-=1
t-=1
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G1[u-1] += [(v-1, a)]
    G1[v - 1] += [(u - 1, a)]
    G2[u-1] += [(v-1, b)]
    G2[v - 1] += [(u - 1, b)]

y_cost = dijkstra(G1, s)
s_cost = dijkstra(G2, t)
ans = [0] * n
ret = INF
for i in range(n - 1, -1, -1):
    ret = min(ret, s_cost[i] + y_cost[i])
    ans[i] = 10**15 - ret

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def Dijkstra(edge,r,i):
  d=[INF]*len(edge) 
  que=[]
  heappush(que,(0,r))
  d[r]=0
  while que:
    dist,node=heappop(que)
    for to,*cost in edge[node]:
      if d[to]>cost[i]+dist:
        d[to]=cost[i]+dist
        heappush(que,(d[to],to))
  return d
n,m,s,t=map(int,input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  e[u]+=[(v,a,b)]
  e[v]+=[(u,a,b)]
INF=10**18
di=Dijkstra(e,s,0)
dj=Dijkstra(e,t,1)
d=sorted(enumerate([i+j for i,j in zip(di,dj)]),key=lambda x:x[1])[::-1]
for i in range(n):
  while d[-1][0]<=i:d.pop()
  print(10**15-d[-1][1])

Submission status: Accepted

Solution code:
import heapq
INF = float('inf')


def dijkstra(s, n, edges, d):
    d = [INF] * n
    d[s] = 0
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvcost, nv in edges[v]:
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


n, m, s, t = map(int, input().split())
s -= 1
t -= 1
edges_yen = [[] for _ in range(n)]
edges_snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges_yen[u].append((a, v))
    edges_yen[v].append((a, u))
    edges_snuuk[u].append((b, v))
    edges_snuuk[v].append((b, u))
d = [INF] * n
d_yen = dijkstra(s, n, edges_yen, d)
d = [INF] * n
d_snuuk = dijkstra(t, n, edges_snuuk, d)
temp = [0] * n  # 場所iで両替した時の最終スヌーク
for i in range(n):
    temp[i] = 10**15 - (d_yen[i] + d_snuuk[i])

ans = [INF] * n
ans[-1] = temp[-1]
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], temp[i])
# print(d_yen)
# print(d_snuuk)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

def main():
    import collections
    import heapq

    class Dijkstra:
        def __init__(self):
            self.e = collections.defaultdict(list)

        def add(self, u, v, d):  # 無向グラフの場合
            self.e[u].append([v, d])
            self.e[v].append([u, d])

        def delete(self, u, v):
            self.e[u] = [_ for _ in self.e[u] if _[0] != v]
            self.e[v] = [_ for _ in self.e[v] if _[0] != u]

        def search(self, s):  # d[i]はsからiまでの最短距離
            d = collections.defaultdict(lambda: float('inf'))
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in self.e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

    n, m, s, t = MI()

    G1 = Dijkstra()  #円だけ
    G2 = Dijkstra()  #スヌースだけ

    for i in range(m):
        u,v,a,b = MI()
        G1.add(u,v,a)
        G2.add(u,v,b)

    D1 = G1.search(s)
    D2 = G2.search(t)

    A = []

    for i in range(1, n + 1):
        A.append((D1[i] + D2[i], i))

    A.sort()

    b = 0
    for i in range(n):
        if i == 0:
            print(10 ** 15 - A[i][0])
        elif i < A[b][1]:
            print(10 ** 15 - A[b][0])
        else:
            while i >= A[b][1]:
                b += 1
            print(10 ** 15 - A[b][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra(s, edge):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


n, m, s, t = map(int, input().split())

e1 = [[] for _ in range(n)]
e2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    e1[u-1].append([a, v-1])
    e1[v-1].append([a, u-1])
    e2[u-1].append([b, v-1])
    e2[v-1].append([b, u-1])

d1 = dijkstra(s-1, e1)
d2 = dijkstra(t-1, e2)
dist = [d1[i] + d2[i] for i in range(n)]

res = [0] * n

min_dist = float('inf')
for i in range(n-1, -1, -1):
    min_dist = min(min_dist, dist[i])
    res[i] = 10 ** 15 - min_dist

for v in res:
    print(v)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra(s, edge):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


def segfunc(x, y):
    '''
    問題に応じて返り値を設定
    '''
    return min(x, y)


def init(a):
    '''
    配列aで初期化
    '''
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def update(k, x):
    '''
    a[k]の値をxに更新
    '''
    k += num - 1
    seg[k] = x
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


def query(p, q):
    '''
    [p, q)についてsegfuncを適用したものを返す
    '''
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


n, m, s, t = map(int, input().split())

e1 = [[] for _ in range(n)]
e2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    e1[u-1].append([a, v-1])
    e1[v-1].append([a, u-1])
    e2[u-1].append([b, v-1])
    e2[v-1].append([b, u-1])

d1 = dijkstra(s-1, e1)
d2 = dijkstra(t-1, e2)
dist = [d1[i] + d2[i] for i in range(n)]

num = (2 ** len(bin(n - 1)) - 2)
ide_ele = float('inf')
seg = [ide_ele] * 2 * num
init(dist)

for i in range(n):
    print(10 ** 15 - query(i, n))