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: Time Limit Exceeded

Solution code:
import heapq
def dijk(s,edge):
    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]]:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
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)
su=dijk(t,edge2)
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])

Submission status: Time Limit Exceeded

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]])  # 無向グラフなら両方追加

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 = [0] * v
    searching_list[a] = 1
    
    while sum(searching_list) > 0:
        # print(searching_list)
        for ii in range(len(searching_list)):
            i = searching_list[ii]
            if i == 1:
                searching_list[ii] = 0
                for j in in_connect_list[ii]:
                    c = j[0]
                    p = j[money_kind] 
                    if out_shortest_list[c] > p + out_shortest_list[ii]:
                        out_shortest_list[c] = p + out_shortest_list[ii]
                        searching_list[c] = 1
                    # else:
                    #     searching_list[c] = 0
    
    return out_shortest_list

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

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: Time Limit Exceeded

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]])  # 無向グラフなら両方追加

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 = [0] * v
    searching_list[a] = 1
    
    while sum(searching_list) > 0:
        # print(searching_list)
        new_search_list = [0] * v
        for ii in range(len(searching_list)):
            i = searching_list[ii]
            if i == 1:
                for j in in_connect_list[ii]:
                    c = j[0]
                    p = j[money_kind] 
                    if out_shortest_list[c] > p + out_shortest_list[ii]:
                        out_shortest_list[c] = p + out_shortest_list[ii]
                        new_search_list[c] = 1
        searching_list = new_search_list
                    # else:
                    #     searching_list[c] = 0
    
    return out_shortest_list

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

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: Time Limit Exceeded

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 = [0] * v
    searching_list[a] = 1
    
    while sum(searching_list) > 0:
        for ii in searching_list:
            i = searching_list[ii]
            if i == 1:
                searching_list[ii] = 0
                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]
                        searching_list[c] = 1
    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: Time Limit Exceeded

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: Time Limit Exceeded

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 = [float("inf")] * 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 = float("inf")
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: Time Limit Exceeded

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]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]].append([C[i][1], C[i][3]])  # 無向グラフなら両方追加
    N[C[i][1]].append([C[i][0], 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: Time Limit Exceeded

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]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

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

import heapq

def dijkstra(s, M):
    D = [float("inf")] * 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 = float("inf")
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: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():
  n, m, s, t = map(int, input().split())
  U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
  csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
  csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
  G_yen = dijkstra(csr_yen, directed=False, indices=s)
  G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
  G = G_yen + G_snuuk
  L = []
  L_append = L.append
  U = 10**15
  now = U
  for i in range(n, 0, -1):
    now = min(now, int(G[i]))
    L_append(U-now)
  print(*L[::-1], sep="\n")
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():
  n, m, s, t = map(int, input().split())
  U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
  csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
  csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
  G_yen = dijkstra(csr_yen, directed=False, indices=s)
  G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
  L = []
  L_append = L.append
  U = 10**15
  now = U
  for i in range(n, 0, -1):
    now = min(now, int(G_yen[i]+G_snuuk[i]))
    L_append(U-now)
  print(*L[::-1], sep="\n")
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():
  n, m, s, t = map(int, input().split())
  U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
  csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
  csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
  G_yen = dijkstra(csr_yen, directed=False, indices=s)
  G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
  L = []
  U = 10**15
  now = U
  for i in range(n, 0, -1):
    now = min(now, int(G_yen[i]+G_snuuk[i]))
    L.append(U-now)
  print(*L[::-1], sep="\n")
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m, s, t = map(int, input().split())
U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
G_yen = dijkstra(csr_yen, directed=False, indices=s)
G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
  now = min(now, int(G_yen[i]+G_snuuk[i]))
  L.append(U-now)
print(*L[::-1], sep="\n")

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m, s, t = map(int, input().split())
U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
G_yen = dijkstra(csr_yen, directed=False, indices=s)
G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
L = np.zeros(n, dtype=np.int64)
U = 10**15
now = U
for i in range(n, 0, -1):
  now = min(now, int(G_yen[i]+G_snuuk[i]))
  L[i-1] = U-now
print(*L, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())
ey=[[10**10]*n for _ in range(n)]
es=[[10**10]*n for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  ey[u-1][v-1]=a
  ey[v-1][u-1]=a
  es[u-1][v-1]=b
  es[v-1][u-1]=b
gy=csgraph_from_dense(ey,null_value=10**10)
gs=csgraph_from_dense(es,null_value=10**10)
dy=dijkstra(gy,indices=s-1)
ds=dijkstra(gs,indices=t-1)
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: Time Limit Exceeded

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 verify(graph, start, n):
    h = []
    for edge in graph[start]:
        heapq.heappush(h, edge)
    cost = [INF for i in range(n)]
    cost[start] = 0
    while(h):
        tcost, cur, tgt = heapq.heappop(h)
        if cost[cur] + tcost < cost[tgt]:
            cost[tgt] = cost[cur] + tcost
            for edge in graph[tgt]:
                heapq.heappush(h, edge)

    return cost

def main():
    money = 10 ** 15
    n,m,s,t = getlist()
    yengraph = [[] for i in range(n)]
    snuukgraph = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = getlist()
        yengraph[a - 1].append((c, a- 1, b - 1))
        yengraph[b - 1].append((c, b-1, a - 1))
        snuukgraph[a - 1].append((d, a-1, b - 1))
        snuukgraph[b - 1].append((d, b-1, a - 1))

    ycost = verify(yengraph, s-1, n)
    scost = verify(snuukgraph, t-1, 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: Time Limit Exceeded

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 verify(graph, start, n):
    h = []
    for edge in graph[start]:
        heapq.heappush(h, edge)
    cost = [INF for i in range(n)]
    cost[start] = 0
    while(h):
        tcost, cur, tgt = heapq.heappop(h)
        if cost[cur] + tcost < cost[tgt]:
            cost[tgt] = cost[cur] + tcost
            for edge in graph[tgt]:
                heapq.heappush(h, edge)

    return cost

def main():
    money = 10 ** 15
    n,m,s,t = getlist()
    yengraph = [[] for i in range(n)]
    snuukgraph = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = getlist()
        yengraph[a - 1].append((c, a- 1, b - 1))
        yengraph[b - 1].append((c, b-1, a - 1))
        snuukgraph[a - 1].append((d, a-1, b - 1))
        snuukgraph[b - 1].append((d, b-1, a - 1))

    ycost = verify(yengraph, s-1, n)
    scost = verify(snuukgraph, t-1, 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: Time Limit Exceeded

Solution code:
from itertools import *

def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist * _len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					return None
	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 = SPFA(yen, s - 1)
ttoi = SPFA(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: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s, type=0):
    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, a, b in E[v]:
            if type != 0:
                a, b = b, a
            tmp_d = d + a
            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())
E = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    E[u-1].append((v-1, a, b))
    E[v-1].append((u-1, a, b))

dist_s = dijkstra(s-1)
dist_t = dijkstra(t-1, 1)
ans = float('inf')
idx = -1
for i in range(N):
    if idx >= i:
        print(10 ** 15 - ans)
        continue
    tmp = float('inf')
    for j in range(i, N):
        if dist_s[j] + dist_t[j] <= tmp:
            tmp = dist_s[j] + dist_t[j]
            ans = tmp
            idx = j
    print(10 ** 15 - ans)

Submission status: Time Limit Exceeded

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 = [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, 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)

Submission status: Time Limit Exceeded

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 = [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, 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)

Submission status: Time Limit Exceeded

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 = [s]
    heapq.heapify([q])

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, 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)

Submission status: Time Limit Exceeded

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 = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, 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)

Submission status: Time Limit Exceeded

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 = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, 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])

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


inf = 10**18
def dijkstra(s,cu):
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

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


da = dijkstra(s,0)
db = dijkstra(t,1)
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])

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(s,cu):
    inf = 10**18
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

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


da = dijkstra(s,0)
db = dijkstra(t,1)
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])

x = 10**15
for i in range(n):
    print(x - res[i])