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:
import sys
from collections import namedtuple
from heapq import heappush, heappop


INF = sys.maxsize
Edge = namedtuple('Edge', 'to yen snuuk')
Vertex = namedtuple('Vertex', 'cost id')

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

edges = [[] for _ in range(n + 1)]

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

costs_in_yen = [INF] * (n + 1)
costs_in_snuuk = [INF] * (n + 1)

q = []

heappush(q, Vertex(0, s))
costs_in_yen[s] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_yen[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.yen < costs_in_yen[edge.to]:
      costs_in_yen[edge.to] = v.cost + edge.yen
      heappush(q, Vertex(costs_in_yen[edge.to], edge.to))
      
heappush(q, Vertex(0, t))
costs_in_snuuk[t] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_snuuk[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.snuuk < costs_in_snuuk[edge.to]:
      costs_in_snuuk[edge.to] = v.cost + edge.snuuk
      heappush(q, Vertex(costs_in_snuuk[edge.to], edge.to))      

# n 年後の手持ち snuuk の最大額
snuuk_in_hand = [0] * (n + 1)

for i in range(n - 1, -1, -1):
  snuuk_in_hand[i] = max(
    snuuk_in_hand[i + 1],
    10**15 - costs_in_yen[i + 1] - costs_in_snuuk[i + 1]
  )

for i in range(0, n):
  print(snuuk_in_hand[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]
gyen = [[] for i in range(n+1)]
gsnu = [[] for i in range(n+1)]
for u,v,a,b in uvab:
  gyen[u].append((v,a))
  gyen[v].append((u,a))
  gsnu[u].append((v,b))
  gsnu[v].append((u,b))
import heapq as hq
def dijkstra(start,graph):
  dist = [10**18]*(n+1)
  dist[start] = 0
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,dd in graph[x]:
      if dist[y] > dist[x]+dd:
        dist[y] = dist[x]+dd
        hq.heappush(q,(dist[y],y))
  return dist
distyen = dijkstra(s,gyen)
distsnu = dijkstra(t,gsnu)
ans = []
for i in range(n,0,-1):
  x = 10**15-(distyen[i]+distsnu[i])
  if i == n:
    ans.append(x)
  else:
    ans.append(max(ans[-1],x))
ans = ans[::-1]
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]
gyen = [[] for i in range(n+1)]
gsnu = [[] for i in range(n+1)]
for u,v,a,b in uvab:
  gyen[u].append((v,a))
  gyen[v].append((u,a))
  gsnu[u].append((v,b))
  gsnu[v].append((u,b))
import heapq as hq
def dijkstra(start,graph):
  dist = [10**18]*(n+1)
  dist[start] = 0
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,dd in graph[x]:
      if dist[y] > dist[x]+dd:
        dist[y] = dist[x]+dd
        hq.heappush(q,(dist[y],y))
  return dist
distyen = dijkstra(s,gyen)
distsnu = dijkstra(t,gsnu)
ans = []
for i in range(n,0,-1):
  x = 10**15-(distyen[i]+distsnu[i])
  if i == n:
    ans.append(x)
  else:
    ans.append(max(ans[-1],x))
ans = ans[::-1]
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
inf = 1145141919810364364
start = 10**15
import heapq

def di(s,fl):
    d = [inf] * n
    used = [1] * n
    d[s] = 0
    used[s] = 0
    lis = []
    
    for a,b in edge[fl][s]:
        heapq.heappush(lis,a*(10**6)+b)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge%(10**6)] == 0:
            continue

        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = 0

        for q in edge[fl][v]:
            if used[q[1]] == 1:
                heapq.heappush(lis,(q[0]+d[v])*(10**6)+q[1])
    return d

n,m,s,t = map(int,input().split())
#0は円、1はスヌーク
edge = [[[] for i in range(n)] for _ in range(2)]

for i in range(m):
    u,v,a,b = map(int,input().split())
    edge[0][u-1].append([a,v-1])
    edge[0][v-1].append([a,u-1])
    edge[1][u-1].append([b,v-1])
    edge[1][v-1].append([b,u-1])
    
a = di(s-1,0)
b = di(t-1,1)
k = start - a[n-1] - b[n-1]
ans = [0] * n

for i in range(n):
    k = max(k , start - (a[n-1-i] + b[n-1-i]))
    ans[n-1-i] = k
    
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline
def dijk(s,edge,n):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
def main():
    n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
    s-=1
    t-=1
    edge1 = [[] for i in range(n)]
    edge2= [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(m):
        x,y,z,w = map(int,input().split())
        edge1[x-1].append([z,y-1])
        edge1[y-1].append([z,x-1])
        edge2[x-1].append([w,y-1])
        edge2[y-1].append([w,x-1])
    en=dijk(s,edge1,n)
    su=dijk(t,edge2,n)
    ans=[]
    aa=10**20
    for i in range(n-1,-1,-1):
        aa=min(aa,en[i]+su[i])
        ans.append(10**15-aa)
    for i in range(n-1,-1,-1):
        print(ans[i])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
 
s -= 1
t -= 1
 
# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト
 
# M = [[] for i in range(n)]
# for i in range(len(C)):
#     M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  # 無向グラフなら両方追加
 
# N = [[] for i in range(n)]
# for i in range(len(C)):
#     N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  # 無向グラフなら両方追加
#     N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  # 無向グラフなら両方追加
 
M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2], C[i][3]])  # 無向グラフなら両方追加
    M[C[i][1]-1].append([C[i][0]-1, C[i][2], C[i][3]])  # 無向グラフなら両方追加
 
import heapq

def dijkstra(a, in_connect_list, v, money_kind): 
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(c)
        searching_list = list(set(new_search_list))  # 元コードから変更
    return out_shortest_list
 
# Ds, _ = dijkstra(s, M)
# Dt, _ = dijkstra(t, N)
 
Ds = dijkstra(s, M, n, 1)
Dt = dijkstra(t, M, n, 2)
 
ANS = [0] * n
 
# print(Ds,Dt)
 
ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans
 
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Accepted

Solution code:
import sys
import heapq
input=sys.stdin.readline
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n,m,s,t=map(int,input().split())
ey=[[] for _ in range(n)]
es=[[] for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  ey[u-1].append([a,v-1])
  ey[v-1].append([a,u-1])
  es[u-1].append([b,v-1])
  es[v-1].append([b,u-1])
dy=dijkstra_heap(s-1,ey)
ds=dijkstra_heap(t-1,es)
accumb=[10*10]*n
accumb[n-1]=int(dy[n-1]+ds[n-1])
for i in range(1,n):
  accumb[n-i-1]=int(min(dy[n-i-1]+ds[n-i-1],accumb[n-i]))
money=10**15
for i in range(n):
  print(money-accumb[i])

Submission status: Accepted

Solution code:
# 「C[i][0]から1を引くのを別のループでやらない」「大きい値にはinfでなく10**16を使う」
# この2つはTLEしないために必須。それでも数回に1回、TLEすることがある

import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

# M = [[] for i in range(n)]
# for i in range(len(C)):
#     M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  # 無向グラフなら両方追加

# N = [[] for i in range(n)]
# for i in range(len(C)):
#     N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  # 無向グラフなら両方追加
#     N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  # 無向グラフなら両方追加

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2], C[i][3]])  # 無向グラフなら両方追加
    M[C[i][1]-1].append([C[i][0]-1, C[i][2], C[i][3]])  # 無向グラフなら両方追加

import heapq

# def dijkstra(s, M):
#     D = [10**16] * n  # 頂点0からの距離
#     P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
#     D[s] = 0
#     V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
#     Q = []  # 優先度付きキュー
#     for v in range(n):
#         heapq.heappush(Q, [D[v], v])

#     le = len(Q)
#     while le > 0:
#         q = heapq.heappop(Q)
#         u = q[1]
#         du = q[0]
#         if V[u] == 0:
#             V[u] = 1
#             le -= 1
#             for i in range(len(M[u])):
#                 v = M[u][i][0]
#                 luv = M[u][i][1]
#                 if V[v] == 0:
#                     alt = du + luv
#                     if D[v] > alt:
#                         D[v] = alt
#                         P[v] = u
#                         heapq.heappush(Q, [alt, v])
#     return D, P

def dijkstra(a,in_connect_list,v,money_kind):
 
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(j[0])
        searching_list = new_search_list
 
    return out_shortest_list

# Ds, _ = dijkstra(s, M)
# Dt, _ = dijkstra(t, N)

Ds = dijkstra(s, M, n, 1)
Dt = dijkstra(t, M, n, 2)

ANS = [0] * n

# print(Ds,Dt)

ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  # 無向グラフなら両方追加

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  # 無向グラフなら両方追加
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  # 無向グラフなら両方追加

import heapq

def dijkstra(s, M):
    D = [10**16] * n  # 頂点0からの距離
    P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
    D[s] = 0
    V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
    Q = []  # 優先度付きキュー
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n

# print(Ds,Dt)

ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

# for i in range(m):
#     for j in range(2):
#         C[i][j] -= 1

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  # 無向グラフなら両方追加

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  # 無向グラフなら両方追加
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  # 無向グラフなら両方追加

import heapq

def dijkstra(s, M):
    D = [10**16] * n  # 頂点0からの距離
    P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
    D[s] = 0
    V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
    Q = []  # 優先度付きキュー
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n

# print(Ds,Dt)

ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
INF=10**18
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[(enc[i]+snc[i],i) for i in range(n)]
heapify(res)
for i in range(n):
    while(res[0][1]<i):
        heappop(res)
    print(10**15-res[0][0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] # 円のグラフ
c = [[] for i in range(n)] # スヌークのグラフ

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    INF=pow(10,15)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=pow(10,15)
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

for i in range(n):
    print(pow(10,15)-ans[i])

Submission status: Accepted

Solution code:
n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] # 円のグラフ
c = [[] for i in range(n)] # スヌークのグラフ

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=float('inf')
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

for i in range(n):
    print(10**15-ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import fractions
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs


def main():
    money = 10 ** 15
    n, m, s, t = getlist()
    s -= 1; t -= 1

    yengraph = [[] for _ in range(n)]
    snuukgraph = [[] for _ in range(n)]
    for i in range(m):
        a, b, c, d = getlist()
        a -= 1; b -= 1
        yengraph[a].append([c, b])
        yengraph[b].append([c, a])
        snuukgraph[a].append([d, b])
        snuukgraph[b].append([d, a])

    ycost = dijkstra(yengraph, s, n)
    scost = dijkstra(snuukgraph, t, n)

    sumcost = []
    idx = 1
    for y, s in zip(ycost, scost):
        sumcost.append((y+s, idx))
        idx += 1
    sumcost.sort()
    idx = 0
    for i in range(n):
        while True:
            ans, cid = sumcost[idx]
            if cid > i:
                print(money - ans)
                break
            else:
                idx += 1
    # print(ycost)
    # print(scost)
    # print(sumcost)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
n,m,s,t = inm()
dst = [{} for i in range(n)]
for i in range(m):
    u,v,a,b = inm()
    dst[u-1][v-1] = (a,b)
    dst[v-1][u-1] = (a,b)

costa = [BIG]*n
costb = [BIG]*n
q = [(0,s-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costa[p]<=d:
        continue
    costa[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][0], v))

q = [(0,t-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costb[p]<=d:
        continue
    costb[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][1], v))

#ddprint(costa)
#ddprint(costb)

mn = BIG
ans = []
for i in range(n-1,-1,-1):
    mn = min(mn, costa[i]+costb[i])
    ans.append(mn)
for i in range(n-1,-1,-1):
    print(10**15-ans[i])

Submission status: Accepted

Solution code:
from heapq import *
from itertools import *


def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D


n, m, s, t, *L = map(int, open(0).read().split())
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for u, v, a, b in zip(*[iter(L)] * 4):
	u -= 1
	v -= 1
	yen[u].append((v, a))
	yen[v].append((u, a))
	snuuk[u].append((v, b))
	snuuk[v].append((u, b))
stoi = Dijkstra(yen, s - 1)
ttoi = Dijkstra(snuuk, t - 1)
rest = [10 ** 15 - x - y for x, y in zip(stoi, ttoi)]
ans = list(accumulate(rest[::-1], max))[::-1]
print(*ans)

Submission status: Accepted

Solution code:
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')
ycost = [INF] * N
ycost[S] = 0
q = [(0,S)]
heapq.heapify(q)
while q:
    c,v = heapq.heappop(q)
    for to,a,b in es[v]:
        if c+a >= ycost[to]: continue
        ycost[to] = c+a
        heapq.heappush(q, (c+a,to))

scost = [INF] * N
scost[T] = 0
q = [(0,T)]
heapq.heapify(q)
while q:
    c,v = heapq.heappop(q)
    for to,a,b in es[v]:
        if c+b >= scost[to]: continue
        scost[to] = c+b
        heapq.heappush(q, (c+b,to))

a = 0
ans = []
for y,s in zip(ycost[::-1],scost[::-1]):
    tmp = 10**15 -y -s
    a = max(a, tmp)
    ans.append(a)
print(*ans[::-1], sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, s, t = map(int, input().split())
e = dd(list)
ee = dd(list)
for i in range(M):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  ee[u].append((v, b))
  ee[v].append((u, b))

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 10)
      v0 = v // (10 ** 10)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 10) + p[0])
    return d
dij = dijkstra(N, e)
edij = dijkstra(N, ee)
p = dij.path(s, 0)
revp = edij.path(t, 0)
mny = pow(10, 15)
table = [0] * (N + 1)
for x in range(1, N + 1):
  table[x] = mny - p[x] - revp[x]
csmx = [0] * (N + 1)

for i in range(N, 0, -1): csmx[i - 1] = max(csmx[i - 1], table[i], csmx[i])
for i in range(N): print(csmx[i])

Submission status: Accepted

Solution code:
import heapq as hq
from collections import defaultdict
n, m, s, t = map(int,input().split())
s -= 1
t -= 1
edges = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edges[u-1].append((v-1, a, b))
    edges[v-1].append((u-1, a, b))
INF = float("inf")
d = [INF]*n
d[s] = 0
q = [(0,s)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, a, b in edges[i]:
        if d[j] > d[i]+a:
            d[j] = d[i]+a
            hq.heappush(q, (d[j], j))
ttoi = [INF]*n
ttoi[t] = 0
q = [(0,t)]
while q:
    dist, i = hq.heappop(q)
    if ttoi[i] < dist:
        continue
    for j, a, b in edges[i]:
        if ttoi[j] > ttoi[i]+b:
            ttoi[j] = ttoi[i]+b
            hq.heappush(q, (ttoi[j], j))
tmp = INF
ans = [None]*n
for i in range(n-1,-1,-1):
    if d[i]+ttoi[i] < tmp:
        tmp = d[i]+ttoi[i]
    ans[i] = 10**15-tmp
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import heapq
INFTY = 10**15
n,m,s,t = map(int,input().split())
G = {}
for _ in range(m):
    u,v,a,b = map(int,input().split())
    if u not in G:
        G[u] = []
    G[u].append((v,a,b))
    if v not in G:
        G[v] = []
    G[v].append((u,a,b))
ce = [INFTY for _ in range(n+1)]
ce[s] = 0
hist = [0 for _ in range(n+1)]
heap = [(0,s)]
hist[s] = 1
while heap:
    c,x = heapq.heappop(heap)
    if c>ce[x]:continue
    hist[x] = 1
    for y,a,_ in G[x]:
        if hist[y]==0:
            if ce[y]>ce[x]+a:
                ce[y] = ce[x]+a
                heapq.heappush(heap,(ce[y],y))
cs = [INFTY for _ in range(n+1)]
cs[t] = 0
hist = [0 for _ in range(n+1)]
heap = [(0,t)]
hist[t] = 1
while heap:
    c,x = heapq.heappop(heap)
    if c>cs[x]:continue
    hist[x] = 1
    for y,_,b in G[x]:
        if hist[y]==0:
            if cs[y]>cs[x]+b:
                cs[y] = cs[x]+b
                heapq.heappush(heap,(cs[y],y))
F = [0 for _ in range(n+1)]
F[0] = INFTY
for i in range(1,n+1):
    F[i] = ce[i]+cs[i]
H = [0 for _ in range(n)]
H[n-1] = F[n]
for i in range(n-2,-1,-1):
    H[i] = min(H[i+1],F[i+1])
for i in range(n):
    print(10**15-H[i])

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s, neighbor):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, l in neighbor[v]:
            tmp_d = d + l
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    snuuk[u-1].append((v-1, b))
    snuuk[v-1].append((u-1, b))

dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
    if dist_s[i] + dist_t[i] < tmp:
        tmp = dist_s[i] + dist_t[i]
    ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))
    


def dijkstra(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    q = [(d[s],s)] # priority queueのソートキーが第一要素
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,c in e[v]:
            if d[v]+c>=d[u]:
                continue
            d[u] = d[v] + c
            heapq.heappush(q, (d[u],u))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

for r in res:
    print(10**15 - r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
e = [[] for _ in range(n+1)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


inf = 10**18
def dijkstra(s,cu):
    d = [inf]*(n+1)
    d[s] = 0

    q = [(d[s],s)]
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[v]+ud[cu]>=d[u]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, (d[u],u))
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n]+db[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i+1]+db[i+1])

for r in res:
    print(10**15 - r)