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: Runtime Error

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 10
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    # ゴールの都市Tで両替するのはNGなことに注意
    city_cost = [(cost, city) for city, cost in enumerate(min_cost) if city != T]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = 10 ** 15 - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

def main():
  n, m, s, t = map(int, input().split())
  
  tree = [[] for _ in range(n)]
  cost_yen = [[0]*n for _ in range(n)]
  cost_snuke = [[0]*n for _ in range(n)]
  for i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuke[u-1][v-1] = b
    cost_snuke[v-1][u-1] = b
  
  ans_yen = [0]*n
  ans_snuke = [0]*n
  
  for cost, start, ans in zip([cost_yen, cost_snuke], [s-1, t-1], [ans_yen, ans_snuke]):
    already = [False]*n
    not_yet = [(0, start)]
    
    while len(not_yet) > 0:
      c, p = heappop(not_yet)
      if already[p]:
        continue
      ans[p] = c
      already[p] = True
      
      for value in tree[p]:
        if already[value]:
          continue
        heappush(not_yet, (ans[p]+cost[p][value], value))
  
  ans = [0]*n
  sub = 10**15
  for i in range(n-1, -1, -1):
    sub = min(sub, ans_yen[i]+ans_snuke[i])
    ans[i] = sub
  
  sub = 10**15
  for a in ans:
    print(sub-a)
      
  
  
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

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), indices=s, directed=False, limit=1e10)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32), indices=t, directed=False, limit=1e10)    
    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: Runtime Error

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


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-sorted(dist[i:])[0])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

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

gy = np.zeros((n, n))
gs = np.zeros((n, n))
for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b


Gy = csgraph_from_dense(gy)
dy = dijkstra(Gy, indices=s-1)

Gs = csgraph_from_dense(gs)
ds = dijkstra(Gs, indices=t-1)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-int(min(dist[i:])))

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m,s,t = map(int,ipt().split())
    s -= 1
    t -= 1
    row = []
    col = []
    cos1 = []
    cos2 = []
    for _ in range(m):
        u,v,a,b = map(int,ipt().split())
        u -= 1
        v -= 1
        row.append(u)
        col.append(v)
        cos1.append(a)
        cos2.append(b)
    csr = csr_matrix((cos1,(row,col)), shape=(n,n))
    d1 = dijkstra(csr,directed=False)
    csr = csr_matrix((cos2,(row,col)), shape=(n,n))
    d2 = dijkstra(csr,directed=False)
    cm = [0]*n
    cm[n-1] = d1[s][n-1]+d2[n-1][t]
    for i in range(n-1):
        w = int(d1[s][n-2-i]+d2[n-2-i][t])
        cmi = cm[n-1-i]
        if w > cm[n-1-i]:
            cm[n-2-i] = cmi
        else:
            cm[n-2-i] = w
    for i in cm:
        print(10**15-int(i))


    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m,s,t = map(int,ipt().split())
    s -= 1
    t -= 1
    row = []
    col = []
    cos1 = []
    cos2 = []
    for _ in range(m):
        u,v,a,b = map(int,ipt().split())
        u -= 1
        v -= 1
        row.append(u)
        col.append(v)
        cos1.append(a)
        cos2.append(b)
    csr = csr_matrix((cos1,(row,col)), shape=(n,n))
    d1 = dijkstra(csr,directed=False)
    csr = csr_matrix((cos2,(row,col)), shape=(n,n))
    d2 = dijkstra(csr,directed=False)
    cm = [0]*n
    cm[n-1] = d1[s][n-1]+d2[n-1][t]
    for i in range(n-1):
        cm[n-2-i] = min(d1[s][n-2-i]+d2[n-2-i][t],cm[n-1-i])
    for i in cm:
        print(10**15-int(i))


    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

N, M, S, T, *UVAB = map(int, open(0).read().split())
A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S, min_only=True)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T, min_only=True)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

Submission status: Runtime Error

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])),i)
    remainingSnuuk.sort(key=lambda x: x[0], reverse=True)

    j = 0
    for i in range(n):
        while remainingSnuuk[j][1] <= i:
            j += 1
        print(remainingSnuuk[j][0])
main()

Submission status: Runtime Error

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].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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kで交換した時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = queue.pop()
        if d[v] < distance:
            continue
        for u in range(len(town[v])):
            if d[town[v][u][0]] > d[v] + town[v][u][k]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
                heapq.heappaush(queue, (d[town[v][u][0]], town[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from queue import PriorityQueue as PQ
INF = float('inf')
def pcc(src):
	pq = PQ()
	global n
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w,v in adj[u]:
			if dist[v] > dist[u]+w:
				dist[v] = dist[u]+w
				pq.put([dist[v], v])
	return dist

n,m,src=(int(i) for i in input().split())
adj = {}
for i in range(n+1): adj[i] = []
for i in range(m):
	u,v,w = (int(i) for i in input().split())
	adj[u].append([w,v])
	adj[v].append([w,u])

dist = pcc(src)

for i in range(n):
	print(i,"\t",dist[i])

Submission status: Runtime Error

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 = [0] * n
for i in range(n):
    cost.append([yen[i + 1] + snu[i + 1], i])

heapq.heapify(cost)
nn,l = heapq.heappop(cost)
for i in range(n):
    while l <= i:
        nn,l = heapq.heappop(cost)
    print(10 ** 15 - nn)

Submission status: Runtime Error

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

def dijkstra(n, graph, s, yen=True):
    dist = [10**18] * n
    queue = [(s, 0)]
    dist[s] = 0
    while queue:
        v, d = heapq.heappop(queue)
        if dist[v] < d:
            continue
        for child, costa, costb in graph[v]:
            if yen:
                cost = costa
            else:
                cost = costb
            if dist[v] + cost < dist[child]:
                dist[child] = dist[v] + cost
                heapq.heappush(queue, (child, dist[child]))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    s_graph = [[] for _ in range(n)]
    t_graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        s_graph[u].append((v, a, b))
        s_graph[v].append((u, a, b))
        t_graph[u].append((v, a, b))
        t_graph[v].append((u, a, b))
    s_dist = dijkstra(n, s_graph, s, True)
    t_dist = dijkstra(n, t_graph, t, False)

    cost = 10 ** 18
    ans = []
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans.append(10 ** 15 - cost)
    for x in reversed(ans):
        pritn(x)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for _ in range(m)]

# import
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

cost_e = np.zeros((n,n))
cost_s = np.zeros((n,n))

for i in uvab:
    u,v,a,b = i
    cost_e[u-1][v-1] = a
    cost_s[u-1][v-1] = b
    cost_e[v-1][u-1] = a
    cost_s[v-1][u-1] = b

csr_e = csr_matrix(cost_e)
csr_s = csr_matrix(cost_s)

# en = shortest_path(csr_e, indices=s-1 ,method='D')
# sn = shortest_path(csr_s, indices=t-1 ,method='D')
en = dijkstra(csr_e, indices=s-1)
sn = dijkstra(csr_s, indices=t-1)


ans = [10**15] * n
min_ = en[n-1] + sn[n-1]
for i in range(n-1, -1, -1):
    tmp = en[i] + sn[i]
    min_ = min(min_, tmp)
    ans[i] -= min_

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

Submission status: Runtime Error

Solution code:
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for _ in range(m)]

# import
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

inf = np.inf

cost_e = np.zeros((n,n))
cost_s = np.zeros((n,n))

for i in uvab:
    u,v,a,b = i
    cost_e[u-1][v-1] = a
    cost_s[u-1][v-1] = b
    cost_e[v-1][u-1] = a
    cost_s[v-1][u-1] = b

csr_e = csr_matrix(cost_e)
csr_s = csr_matrix(cost_s)

en = shortest_path(csr_e, indices=s-1 ,method='D')
sn = shortest_path(csr_s, indices=t-1 ,method='D')

ans = [10**15] * n
min_ = en[n-1] + sn[n-1]
for i in range(n-1, -1, -1):
    tmp = en[i] + sn[i]
    min_ = min(min_, tmp)
    ans[i] -= min_

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())

s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = coo_matrix((a, (u, v)), shape=(n, n))
snuuk_matrix = coo_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s, limit=10 ** 15)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t, limit=10 ** 15)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), sep='\n')

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
if n == m == 10 ** 5:
    from heapq import heappush, heappop

    N, M, S, T = n, m, s, t
    graph = [[] for _ in range(N + 1)]
    for u, v, a, b in zip(*[iter(uvab)] * 4):
        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
        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


    d1 = np.array(dijkstra(S, 0))
    d2 = np.array(dijkstra(T, 1))

    d1 += d2
    answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
    print('\n'.join(answer.astype(str)))
    exit()
s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = coo_matrix((a, (u, v)), shape=(n, n), dtype=float_)
snuuk_matrix = coo_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), sep='\n')

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
u = np.array(uvab[::4], np.int64)
v = np.array(uvab[1::4], np.int64)
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = csr_matrix((a, (u, v)), shape=(n + 1, n + 1))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n + 1, n + 1))

yen = shortest_path(yen_matrix, directed=False, indices=s)[1:]
snuuk = shortest_path(snuuk_matrix, directed=False, indices=t)[1:]

costs = (yen + snuuk).astype(int)
costs = sorted(zip(range(1, n + 1), costs.tolist()), key=itemgetter(1), reverse=True)

money = 10 ** 15
city, cost = costs.pop()
for i in range(n):
    if city <= i:
        while True:
            city, cost = costs.pop()
            if city > i:
                break
    print(money - cost)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

edges = defaultdict(dict)
for i in range(1, M + 1):
    u, v, a, b = map(int, input().split())
    edges[u][v] = {"a": a, "b": b}
    edges[v][u] = {"a": a, "b": b}

inf = float('inf')
costs_from_S_by_y = defaultdict(int)
costs_to_T_by_s = defaultdict(int)


def find_lowest_cost_node(costs, processed):
    lowest_cost = inf
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Sから両替所候補となる各ノードへの円を使った最短距離を計算する
temp_processed = []

temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is S:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["a"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_from_S_by_y[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)

print(f"costs_from_S_by_y={costs_from_S_by_y}")

# 両替所候補となる各ノードからTへのスヌークを使った最短距離を計算する
temp_processed = []

temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is T:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["b"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_to_T_by_s[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)

print(f"costs_to_T_by_s={costs_to_T_by_s}")


# S->i + i->T の合計コスト
total_costs = []
for i in range(1, N + 1):
    total_costs.append(costs_from_S_by_y[i] + costs_to_T_by_s[i])
print(f"total_costs={total_costs}")

for i in range(N):
    print((10 ** 15) - min(total_costs[i:]))