Problem p03305 (python)

Fixed submission:
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,S-1)


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,T-1)

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)

Buggy submission (verdict: Runtime Error):
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].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)

Buggy submission (verdict: Runtime Error):
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
    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,Q[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]:
            continue
        else:
            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)

Buggy submission (verdict: Runtime Error):
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=[]
gor 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)

Buggy submission (verdict: Runtime Error):
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))))