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

Solution (Python):
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])

Solution (Python):
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')

Solution (Python):

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)] 
    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)

Solution (Python):

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)

Solution (Python):

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

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

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

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

Solution (Python):
import numpy as np
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

n,m,s,t = map(int, input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    graph[u].append([v,a,b])
    graph[v].append([u,a,b])
money = dijkstra(s,0)
snu = dijkstra(t,1)
start = 10**15

ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 
pque = []
heapq.heappush(pque, [0, s]) 

while len(pque) != 0: 
    p = heapq.heappop(pque) 
    v = p[1] 
    if d1[v] < p[0]: 
        continue
    for i in range(len(g1[v])): 
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: 
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) 



d2[t] = 0 
pque = []
heapq.heappush(pque, [0, t]) 

while len(pque) != 0: 
    p = heapq.heappop(pque) 
    v = p[1] 
    if d2[v] < p[0]: 
        continue
    for i in range(len(g2[v])): 
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: 
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) 



tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

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

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 
pque = []
heapq.heappush(pque, [0, s]) 

while len(pque) != 0: 
    p = heapq.heappop(pque) 
    v = p[1] 
    if d1[v] < p[0]: 
        continue
    for i in range(len(g1[v])): 
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: 
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) 



d2[t] = 0 
pque = []
heapq.heappush(pque, [0, t]) 

while len(pque) != 0: 
    p = heapq.heappop(pque) 
    v = p[1] 
    if d2[v] < p[0]: 
        continue
    for i in range(len(g2[v])): 
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: 
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) 



tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

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

Solution (Python):
import heapq
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())
edge1=[[] for i in range(n)]
edge2=[[] for i in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    edge1[u-1].append(a*(10**6)+(v-1))
    edge1[v-1].append(a*(10**6)+(u-1))
    edge2[u-1].append(b*(10**6)+(v-1))
    edge2[v-1].append(b*(10**6)+(u-1)) 

def dijkstra_heap(edge,s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d

d1=dijkstra_heap(edge1,s-1)
d2=dijkstra_heap(edge2,t-1)
d=[0]*n

for i in range(n):
  d[i]=d1[i]+d2[i]
for i in range(n-1):
  d[-i-2]=min(d[-i-2],d[-i-1])
for dd in d:
  print(10**15-dd)

Solution (Python):
import heapq
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())
edge1=[[] for i in range(n)]
edge2=[[] for i in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    edge1[u-1].append(a*(10**6)+(v-1))
    edge1[v-1].append(a*(10**6)+(u-1))
    edge2[u-1].append(b*(10**6)+(v-1))
    edge2[v-1].append(b*(10**6)+(u-1)) 

def dijkstra_heap(edge,s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d

d1=dijkstra_heap(edge1,s-1)
d2=dijkstra_heap(edge2,t-1)
d=[0]*n

for i in range(n):
  d[i]=d1[i]+d2[i]
for i in range(n-1):
  d[-i-2]=min(d[-i-2],d[-i-1])
for dd in d:
  print(10**15-dd)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


N, M, S, T = map(int, input().split())
PATH = [[] for _ in range(N+1)]


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


def dijkstra(s, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[s] = 0
    que = [(0, s)]

    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue

        for u, *a in PATH[v]:
            dv = d + a[mode]

            if dv < dist[u]:
                dist[u] = dv
                heappush(que, (dv, u))

    return dist


da = dijkstra(S, 0)
db = dijkstra(T, 1)

score = [10**15 - (da[i]+db[i]) for i in range(1, N+1)]

ans = [10**15] * N
ans[-1] = score[-1]

for i in range(N-2, -1, -1):
    ans[i] = max(ans[i+1], score[i])

for i in range(N):
    print(ans[i])

Solution (Python):

from heapq import heappop, heappush
import numpy as np




N, M, S, T = list(map(int, input().split()))
graph = [[] for _ in range(N+1)] 
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    
    INF = 10 ** 15
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))

Solution (Python):
import sys
from heapq import heappop, heappush
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

N, M, S, T = list(map(int, input().split()))
graph = [[] for _ in range(N+1)] 
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    
    INF = 10 ** 15
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))

Solution (Python):
import sys
from heapq import heappop, heappush
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

N, M, S, T = rl()
graph = [[] for _ in range(N+1)] 
for _ in range(M):
    u, v, a, b = rl()
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    
    INF = 10 ** 15
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))

Solution (Python):
from heapq import*
def D(s,e):
 g=10**6;d=[10**18]*n;f=[1]*n;d[s]=f[s]=0;q=[]
 for a,b in e[s]:heappush(q,a*g+b)
 while q:
  m=heappop(q)
  if f[m%g]:
   v=m%g;x=d[v]=m//g;f[v]=0
   for y,w in e[v]:
    if f[w]:heappush(q,(x+y)*g+w)
 return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)];e,f=eval('[[]for _ in"_"*n],'*2);A,m=[],0
for u,v,a,b in z:u-=1;v-=1;e[u]+=(a,v),;e[v]+=(a,u),;f[u]+=(b,v),;f[v]+=(b,u),
for y,s in zip(D(s-1,e)[::-1],D(t-1,f)[::-1]):m=max(m,10**15-y-s);A+=m,
print(*A[::-1])

Solution (Python):
from heapq import*
def D(s,e):
 g=10**6;d=[10**18]*n;f=[1]*n;d[s]=f[s]=0;q=[]
 for a,b in e[s]:heappush(q,a*g+b)
 while q:
  m=heappop(q)
  if f[m%g]:
   v=m%g;x=d[v]=m//g;f[v]=0
   for y,w in e[v]:
    if f[w]:heappush(q,(x+y)*g+w)
 return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)];e,f=eval('[[]for _ in"_"*n],'*2)
for u,v,a,b in z:u-=1;v-=1;e[u]+=(a,v),;e[v]+=(a,u),;f[u]+=(b,v),;f[v]+=(b,u),
a,m=[],0
for y,s in zip(D(s-1,e)[::-1],D(t-1,f)[::-1]):m=max(m,10**15-y-s);a+=m,
print(*a[::-1])

Solution (Python):
from heapq import*
def dijkstra(s,e):
 g=10**6;d=[10**18]*n;f=[1]*n;d[s]=f[s]=0;q=[]
 for a,b in e[s]:heappush(q,a*g+b)
 while q:
  m=heappop(q)
  if f[m%g]:
   v=m%g;x=d[v]=m//g;f[v]=0
   for y,w in e[v]:
    if f[w]:heappush(q,(x+y)*g+w)
 return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)]
e,f=eval('[[]for _ in"_"*n],'*2)
for u,v,a,b in z:u-=1;v-=1;e[u]+=(a,v),;e[v]+=(a,u),;f[u]+=(b,v),;f[v]+=(b,u),
a,m=[],0
for y,s in zip(dijkstra(s-1,e)[::-1],dijkstra(t-1,f)[::-1]):m=max(m,10**15-y-s);a+=m,
print(*a[::-1])

Solution (Python):
from heapq import*
def dijkstra(s,e):
  g=10**6;d=[10**18]*n;f=[1]*n;d[s]=f[s]=0;q=[]
  for a,b in e[s]:heappush(q,a*g+b)
  while q:
    m=heappop(q)
    if f[m%g]<1:continue
    v=m%g
    x=d[v]=m//g
    f[v]=0
    for y,w in e[v]:
      if f[w]:heappush(q,(x+y)*g+w)
  return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)]
e,f=eval('[[]for _ in"_"*n],'*2)
for u,v,a,b in z:
  u-=1
  v-=1
  e[u]+=(a,v),
  e[v]+=(a,u),
  f[u]+=(b,v),
  f[v]+=(b,u),
a=[]
m=0
for y,s in zip(dijkstra(s-1,e)[::-1],dijkstra(t-1,f)[::-1]):
  m=max(m,10**15-y-s)
  a+=m,
print(*a[::-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

def Dijkstra(num, start, vedge):
    """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
    """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
    """ dist[i] は start から i までの最短距離 """

    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in vedge[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist




def solve():
    n, m, s, t = LI()
    s -= 1
    t -= 1
    uva = defaultdict(list)
    uvb = defaultdict(list)
    for _ in range(m):
        u, v, a, b = LI_()
        a += 1
        b += 1
        uva[u].append((v, a))
        uva[v].append((u, a))
        uvb[u].append((v, b))
        uvb[v].append((u, b))
    dista = Dijkstra(n, s, uva)
    distb = Dijkstra(n, t, uvb)
    a = [None] * n
    for i in range(n):
        a[i] = dista[i] + distb[i]
    a = a[::-1]
    for i in range(1,n):
        a[i] = min(a[i], a[i - 1])
    a = a[::-1]
    for i in range(n):
        print(10**15-a[i])
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import heapq

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

dic = {}

for i in range(m):

    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,a,b])
    dic[v].append([u,a,b])



q = [[0,t]]

yen = [float("inf")] * n
yen[t] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[2]:
            yen[vab[0]] = yen[du[1]] + vab[2]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])

sunk = yen.copy()


q = [[0,s]]

yen = [float("inf")] * n
yen[s] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[1]:
            yen[vab[0]] = yen[du[1]] + vab[1]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])


cost = []

for i in range(n):
    cost.append( yen[i] + sunk[i] )

costq = []

for i in range(n):
    heapq.heappush(costq , [cost[i] , i])

for i in range(n):

    while costq[0][1] < i:
        heapq.heappop(costq)

    print (10 ** 15 - costq[0][0])

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


N, M, s, t = map(int, input().split())  
s -= 1
t -= 1

graph = Graph()
reverse_graph = Graph()
for _ in range(M):
    u, v, a, b = map(int, input().split())  
    u -= 1
    v -= 1
    graph.add_edge(u, v, a)
    graph.add_edge(v, u, a)
    reverse_graph.add_edge(u, v, b)
    reverse_graph.add_edge(v, u, b)


shortest_from_start = Dijkstra(graph, s)
shortest_from_goal = Dijkstra(reverse_graph, t)



price = shortest_from_start.shortest_distance(N-1)+shortest_from_goal.shortest_distance(N-1)
ans = [price]  


for i in reversed(range(N-1)):  
    ans.append(min(ans[-1], shortest_from_start.shortest_distance(i)+shortest_from_goal.shortest_distance(i)))
ans.reverse()

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    v2 = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
        v2[a].append((b,d))
        v2[b].append((a,d))
    d = [float("inf")]*n
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            nd = dx+c
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    d2 = [float("inf")]*n
    d2[t] = 0
    q = [(0,t)]
    while q:
        dx,x = heappop(q)
        for y,c in v2[x]:
            nd = dx+c
            if nd < d2[y]:
                d2[y] = nd
                heappush(q,(nd,y))
    ans = [10**15-(d[i]+d2[i]) for i in range(n)]
    for i in range(n-1)[::-1]:
        if ans[i+1] > ans[i]:
            ans[i] = ans[i+1]
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, a, b]) for u, v, a, b in uvab]
    [g[v-1].append([u-1, a, b]) for u, v, a, b in uvab]

    import heapq

    yen = np.full(n, np.inf)
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == np.inf:
            yen[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+y, x))

    snk = np.full(n, np.inf)
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == np.inf:
            snk[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+z, x))

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, a, b]) for u, v, a, b in uvab]
    [g[v-1].append([u-1, a, b]) for u, v, a, b in uvab]

    import heapq

    inf = 10**15

    yen = [inf for _ in [0]*n]
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == inf:
            yen[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+y, x))

    snk = [inf for _ in [0]*n]
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == inf:
            snk[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+z, x))

    cost = [yen[i]+snk[i] for i in range(n)]
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    for i in cost:
        print(10**15-i)


main()

Solution (Python):
from itertools import accumulate


def dijkstra(n, s, adj_list):
    
    
    from heapq import heappush, heappop

    dists = [float('inf')] * n
    dists[s] = 0
    heap, rem = [(0, s)], n - 1

    while heap and rem:
        cost, src = heappop(heap)
        if dists[src] < cost:
            continue
        rem -= 1

        for dest, _cost in adj_list[src]:
            newcost = cost + _cost
            if dists[dest] > newcost:
                dists[dest] = newcost
                heappush(heap, (newcost, dest))

    return dists


N, M, S, T = map(int, input().split())
S -= 1
T -= 1
adj_yen = [[] for _ in range(N)]
adj_snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    adj_yen[u].append((v, a))
    adj_yen[v].append((u, a))
    adj_snuuk[u].append((v, b))
    adj_snuuk[v].append((u, b))
yen_cost = dijkstra(N, S, adj_yen)
snuuk_cost = dijkstra(N, T, adj_snuuk)
ans = list(accumulate([10**15-yen-snuuk for yen, snuuk in zip(yen_cost, snuuk_cost)][::-1], max))[::-1]
print('\n'.join(map(str, ans)))

Solution (Python):
import heapq


def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    
    d = [inf for i in range(n)]
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for cost,to in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d


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

yen = [[] for i in range(n)]
snuke = [[] for i in range(n)]

for i in range(m):
    u,v,a,b = train[i]
    u-=1
    v-=1
    yen[u].append([a,v])
    yen[v].append([a,u])
    snuke[u].append([b,v])
    snuke[v].append([b,u])

from_s = dijkstra(s,yen)
to_t = dijkstra(t,snuke)

left = [0 for i in range(n)]
left[-1]=from_s[n-1]+to_t[n-1]


for i in range(1,n):
    left[-i-1]=min(left[-i],from_s[-i-1]+to_t[-i-1])

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