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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(n: int, m: int, s: int, t: int, u: "List[int]", v: "List[int]", a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import coo_matrix 
    from scipy.sparse.csgraph import dijkstra
    from itertools import accumulate
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32).tocsr(), indices=s, directed=False)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32).tocsr(), indices=t, directed=False)
    return []
    acc = list(accumulate(map(int, (ymat+smat)[-1:0:-1].tolist()), min))
    return (10 ** 15 - a for a in reversed(acc))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    m = int(next(tokens))  # type: int
    s = int(next(tokens))  # type: int
    t = int(next(tokens))  # type: int
    u = [int()] * (m)  # type: "List[int]"
    v = [int()] * (m)  # type: "List[int]"
    a = [int()] * (m)  # type: "List[int]"
    b = [int()] * (m)  # type: "List[int]"
    for i in range(m):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(n, m, s, t, u, v, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

# 各都市に対して、
# (1)Sから到達したときの円貨の最小値
# (2)Gから到達したときのスヌークの最小値
# をダイクストラで求める。
# 各都市で両替したときのコストは、(1)と(2)の和である。
# 年を逆順に遡って、順に両替所が開設されると仮定する。
# 新規に開設された(1)と(2)の和が最小値を更新するようであれば更新。最小値がその年の答え。
# コストは最大でも(10 ** (9 + 5)) * 2程度であるため、所持金は超えない。最後に引けばOK。

N,M,S,T = map(int,readline().split())
G = [[] for i in range(N)]
for i in range(M):
  u,v,a,b = map(int,readline().split())
  G[u - 1].append((v - 1, a, b))
  G[v - 1].append((u - 1, a, b))

INF = 10 ** 14 + 1

import heapq as hq
# ダイクストラ
# グラフ, 取るべきコストのindex(円:1, スヌーク:2), 開始点
def get_min_cost(G, label, start):
  dist_from_start = [INF] * len(G)
  # そこまでのコスト, 頂点, 親
  q = [(0, start, -1)]
  hq.heapify(q)
  while q:
    cost, v, parent = hq.heappop(q)
    if dist_from_start[v] <= cost:
      continue
    dist_from_start[v] = cost
    for child in G[v]:
      if child[0] == parent:
        continue
      hq.heappush(q, (dist_from_start[v] + child[label], child[0], v))
  return dist_from_start
  
dist_from_s = get_min_cost(G, 1, S - 1)
dist_from_g = get_min_cost(G, 2, T - 1)

best = INF
ans = [0] * N
wallet = 10 ** 15
for i in range(N - 1, -1, -1):
  # 逆順に両替所を更新していく
  if dist_from_s[i] + dist_from_g[i] < best:
    best = dist_from_s[i] + dist_from_g[i]
  ans[i] = wallet - best

for a in ans:
  print(a)

Submission status: Wrong Answer

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

# 各都市に対して、
# (1)Sから到達したときの円貨の最小値
# (2)Gから到達したときのスヌークの最小値
# をダイクストラで求める。
# 各都市で両替したときのコストは、(1)と(2)の和である。
# 年を逆順に遡って、順に両替所が開設されると仮定する。
# 新規に開設された(1)と(2)の和が最小値を更新するようであれば更新。最小値がその年の答え。
# コストは最大でも(10 ** (9 + 5)) * 2程度であるため、所持金は超えない。最後に引けばOK。

N,M,S,T = map(int,readline().split())
G = [[] for i in range(N)]
for i in range(M):
  u,v,a,b = map(int,readline().split())
  G[u - 1].append((v - 1, a, b))
  G[v - 1].append((u - 1, a, b))

INF = 10 ** 14 + 1

import heapq as hq
# ダイクストラ
# グラフ, 取るべきコストのindex(円:1, スヌーク:2), 開始点
def get_min_cost(G, label, start):
  dist_from_start = [INF] * len(G)
  # 頂点, そこまでのコスト, 親
  q = [(start, 0, -1)]
  hq.heapify(q)
  while q:
    v, cost, parent = hq.heappop(q)
    if dist_from_start[v] <= cost:
      continue
    dist_from_start[v] = cost
    for child in G[v]:
      if child[0] == parent:
        continue
      hq.heappush(q, (child[0], dist_from_start[v] + child[label], v))
  return dist_from_start
  
dist_from_s = get_min_cost(G, 1, S - 1)
dist_from_g = get_min_cost(G, 2, T - 1)

best = INF
ans = [0] * N
wallet = 10 ** 15
for i in range(N - 1, -1, -1):
  # 逆順に両替所を更新していく
  if dist_from_s[i] + dist_from_g[i] < best:
    best = dist_from_s[i] + dist_from_g[i]
  ans[i] = wallet - best

for a in ans:
  print(a)

Submission status: Wrong Answer

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

import heapq

def dijkstra(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())
s,t=s-1,t-1
edge1=[[] for _ in range(n)]
edge2=[[] for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  edge1[u-1].append([a,v-1])
  edge1[v-1].append([a,u-1])
  edge2[u-1].append([b,v-1])
  edge2[v-1].append([b,u-1])
d1=dijkstra(s,edge1)
d2=dijkstra(t,edge1)
INF=10**15
ans=[INF]*n
ans[n-1]=int(d1[n-1]+d2[n-1])
for i in range(n-2,-1,-1):
  tmp=int(d1[i]+d2[i])
  ans[i]=min(tmp,ans[i+1])
for i in range(n):
  print(INF-ans[i])

Submission status: Wrong Answer

Solution code:
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
def main():
    import sys
    input = sys.stdin.readline
    import heapq
    n,m,s,t = map(int,input().split())
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))

    yenEdges = [[] for _ in range(n+1)]
    snuukEdges = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        yenEdges[u].append((v,a))
        yenEdges[v].append((u,a))
        snuukEdges[u].append((v,b))
        snuukEdges[v].append((u,b))
    yenDic = {}
    snuukDic = {}

    dijkstra(yenEdges,yenDic,s)
    dijkstra(snuukEdges,snuukDic,t)

    remainingSnuuk = []
    for i in range(1,n+1):
        remainingSnuuk.append(((10**15-(yenDic[i]+snuukDic[i]))*-1,i))
    heapq.heapify(remainingSnuuk)

    k = 0
    for i in range(n):
        if k <= i:
            r,k = heapq.heappop(remainingSnuuk)
        print(r*-1)
main()

Submission status: Wrong Answer

Solution code:
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
import heapq
n,m,s,t = map(int,input().split())
def dijkstra(edges,costDic,startPoint):
    que=[(0,startPoint)]
    heapq.heapify(que)
    while que:
        cost,now = heapq.heappop(que)
        if now not in costDic:
            costDic[now] = cost
            for nx,c in edges[now]:
                if nx not in costDic:
                    heapq.heappush(que,(cost+c,nx))

yenEdges = [[] for _ in range(n+1)]
snuukEdges = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int,input().split())
    yenEdges[u].append((v,a))
    yenEdges[v].append((u,a))
    snuukEdges[u].append((v,b))
    snuukEdges[v].append((u,b))
yenDic = {}
snuukDic = {}

dijkstra(yenEdges,yenDic,s)
dijkstra(snuukEdges,snuukDic,t)

remainingSnuuk = []
for i in range(1,n+1):
    remainingSnuuk.append(((10**15-(yenDic[i]+snuukDic[i]))*-1,i))
heapq.heapify(remainingSnuuk)

k = 0
for i in range(n):
    if k <= i:
        r,k = heapq.heappop(remainingSnuuk)
    print(r*-1)

Submission status: Wrong Answer

Solution code:
import heapq
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))

def dijkstra(s, n):
    inf = 10**18
    d = [inf]*N
    d[s] = 0
    h = []
    for e in E[s]:
        heapq.heappush(h, (e[n], e[0]))
    while h:
        temp = heapq.heappop(h)
        r = temp[0]
        u = temp[1]
        d[u] = r
        for e in E[u]:
            if d[e[0]] <= r+e[n]:
                continue
            heapq.heappush(h, (r+e[n], e[0]))
    return d

money = 10**15
A = dijkstra(S-1, 1)
B = dijkstra(T-1, 2)
ans = [0]*(N+1)

for i in range(N-1, -1, -1):
    ans[i] = max(ans[i+1], money-A[i]-B[i])
    
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import heapq
N,M,S,T = map(int,input().split())

adj=[[] for _ in range(N)]

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].append((b-1,c,d))
    adj[b-1].append((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,0)


while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen<D_S[next_node]:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_S[next_node]*N+next_node)

Q=[]
heapq.heappush(Q,0)

while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen<D_T[next_node]:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_T[next_node]*N+next_node)


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

Solution code:
import heapq
N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,0)


while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen<D_S[next_node]:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_S[next_node]*N+next_node)

Q=[]
heapq.heappush(Q,0)

while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen<D_T[next_node]:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_T[next_node]*N+next_node)


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

Solution code:
import heapq
N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

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

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

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

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[N+1]*N
D_T=[N+1]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

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

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[N+1]*N
D_T=[N+1]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=N+1
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

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

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[N+1]*N
D_T=[N+1]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=N+1
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

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

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


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

Submission status: Wrong Answer

Solution code:
import heapq

N,M,S,T = map(int,input().split())

adj=[set()]*N

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,(0,S-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_S[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_S[next_node]:
            continue
        else:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_S[next_node],next_node))

Q=[]
heapq.heappush(Q,(0,T-1))


while Q:

    dist_to_node,node = heapq.heappop(Q)
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen>=D_T[next_node]:
            continue
        else:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,(D_T[next_node],next_node))


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)

print("\n".join(map(lambda x:str(10**15-x),reversed(ans))))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N,M,S,T = map(int,input().split())

mat_s=[[N+1]*N for _ in range(N)]
mat_t=[[N+1]*N for _ in range(N)]
for _ in range(M):
    a,b,c,d = map(int,input().split())
    mat_s[a-1][b-1]=c
    mat_s[b-1][a-1]=c
    mat_t[a-1][b-1]=d
    mat_t[b-1][a-1]=d

D_S= dijkstra(csgraph=csr_matrix(mat_s),directed=False,indices=S-1)
D_T= dijkstra(csgraph=csr_matrix(mat_s),directed=False,indices=T-1)


ans=[None]*N

for i in range(N):
    ans[i]= D_S[i]+D_T[i]

tmp=float("inf")

ans_list=[]
for i in reversed(range(N)):
    tmp = min(tmp,ans[i])
    ans_list.append(int(10**15-tmp))
print("\n".join(map(str,reversed(ans_list))))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N,M,S,T = map(int,input().split())

mat_s=[[float('inf')]*N for _ in range(N)]
mat_t=[[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a,b,c,d = map(int,input().split())
    mat_s[a-1][b-1]=c
    mat_s[b-1][a-1]=c
    mat_t[a-1][b-1]=d
    mat_t[b-1][a-1]=d

D_S= dijkstra(csgraph=csr_matrix(mat_s),directed=False,indices=S-1)
D_T= dijkstra(csgraph=csr_matrix(mat_s),directed=False,indices=T-1)


ans=[None]*N

for i in range(N):
    ans[i]= D_S[i]+D_T[i]

tmp=float("inf")

ans_list=[]
for i in reversed(range(N)):
    tmp = min(tmp,ans[i])
    ans_list.append(int(10**15-tmp))
print("\n".join(map(str,reversed(ans_list))))

Submission status: Wrong Answer

Solution code:
import heapq
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())

y_edge = [[] for i in range(n)]
s_edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,yen,strc = map(int,input().split())
    y_edge[x-1].append([yen,y-1])
    y_edge[y-1].append([yen,x-1])
    s_edge[x-1].append([strc,y-1]) 
    s_edge[y-1].append([strc,x-1])

y_dis = dijkstra_heap(s-1,y_edge)
y_dis = y_dis[::-1]
s_dis = dijkstra_heap(t-1,s_edge)
s_dis = s_dis[::-1]
dis = [y_dis[i] + s_dis[i] for i in range(n)]

mn = 10**9
ans = []

for i in range(n):
    mn = min(mn,dis[i])
    ans.append(10**15-mn)
ans = ans[::-1]

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import heapq
INF = 10**100

def dijkstra(N, s, i):
  visited = [False]*(N+1)
  costs = [INF]*(N)
  costs[s-1] = 0

  pq = [(0,s)]
  while pq:
    c, n = pq.pop(0)
    visited[n] = True
    for nei,*fee in adj_list[n]:
      if visited[nei]: continue
      if c+fee[i] < costs[nei-1]:
        costs[nei-1] = c+fee[i]
        pq.append((costs[nei-1],nei))

  return costs

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

yen_costs = dijkstra(n, s, 0)
snk_costs = dijkstra(n, t, 1)
total_costs = list(map(sum, zip(yen_costs, snk_costs)))
comp = INF
res = []
for c in reversed(total_costs):
  if c < comp:
    res.append(int(1e15 - c))
    comp = c
  else:
    res.append(int(1e15 - comp))

print("\n".join(map(str, reversed(res))))

Submission status: Wrong Answer

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

cost_a = [[float("inf")] * (n+1) for _ in range(n+1)]
cost_b = [[float("inf")] * (n+1) for _ in range(n+1)]

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

d_a = [float("inf")] * (n+1)
d_a[s] = 0
d_b = [float("inf")] * (n+1)
d_b[t] = 0
visit_a = [False] * (n+1)
visit_b = [False] * (n+1)

while True:
    v = -1
    for i in range(1, n+1):
        if v == -1 and not visit_a[i]:
            v = i
        elif d_a[i] < d_a[v] and not visit_a[i]:
            v = i
    if v == -1:
        break
    visit_a[v] = True
    
    for j in range(1, n+1):
        d_a[j] = min(d_a[j], d_a[v] + cost_a[v][j])
        
while True:
    v = -1
    for i in range(1, n+1):
        if v == -1 and not visit_b[i]:
            v = i
        elif d_b[i] < d_b[v] and not visit_b[i]:
            v = i
    if v == -1:
        break
    visit_b[v] = True
    
    for j in range(1, n+1):
        d_b[j] = min(d_b[j], d_b[v] + cost_b[v][j])
    
anses = [0] * n
ans = 10**15
for i in range(n):
    ans = min(ans, d_a[n-1-i]+d_b[n-1-i])
    anses[n-1-i]=10**15-ans
for i in range(n):
    print(anses[i])

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[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 graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[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 graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [[float("INF"),float("INF")]] * (n + 1)
for i in range(1, n + 1):
    cost[i] = [yen[i] + snu[i],i]

heapq.heapify(cost)
c = -1
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(10 ** 15 - nn)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[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 graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[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 graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

print(yen,"\n",snu)
cost = [float("INF")] * (n + 1)
for i in range(1, n + 1):
    cost[i] = (yen[i] - yen[s]) + snu[i]

for i in range(1, n + 1):
    print(1000000000000000 - min(cost))
    del cost[1]