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:
import heapq
import sys
input=sys.stdin.readline
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]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
def main():
    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])
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = np.zeros((n+1,n+1))
snu = np.zeros((n+1,n+1))
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u][v] = money[v][u] = a
    snu[u][v] = snu[v][u] = b
money = dijkstra(csr_matrix(money))
snu = dijkstra(csr_matrix(snu))
start = 10**15
#何年目か？
for i in range(n):
    ans = 0
    #i年目なので、iまででは両替出来ない。両替する場所を探す
    for j in range(i+1,n+1):
        ans = max(ans, start - (money[s][j] + snu[j][t]))
    print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = np.zeros((n+1,n+1))
snu = np.zeros((n+1,n+1))
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u][v] = money[v][u] = a
    snu[u][v] = snu[v][u] = b
money = dijkstra(csr_matrix(money))
snu = dijkstra(csr_matrix(snu))
for i in range(n):
    ans = 0
    for j in range(i+1,n+1):
        ans = max(ans, (10**15) - (money[s][j] + snu[j][t]))
    print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
n,m,s,t = map(int, input().split())
money = np.zeros((n+1,n+1))
snu = np.zeros((n+1,n+1))
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u][v] = money[v][u] = a
    snu[u][v] = snu[v][u] = b
money = dijkstra(csr_matrix(money))
snu = dijkstra(csr_matrix(snu))
for i in range(n):
    ans = 0
    for j in range(i+1,n+1):
        ans = max(ans, (10**15) - (money[s][j] + snu[j][t]))
    print(int(ans))

Submission status: Runtime Error

Solution code:
def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import shortest_path

    input = sys.stdin.readline

    MAX  = 10 ** 15

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

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = shortest_path(g1, directed = False, indices = s - 1, method = 'D')
    d2 = shortest_path(g2, directed = False, indices = t - 1, method = 'D')

    d = d1 + d2

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d[i])
        ans[i] -= int(tmp)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import shortest_path

    input = sys.stdin.readline

    MAX  = 10 ** 15

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

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = shortest_path(g1, directed = False, indices = s - 1, method = 'auto')
    d2 = shortest_path(g2, directed = False, indices = t - 1, method = 'auto')

    d = d1 + d2

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d[i])
        ans[i] -= int(tmp)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.INFO)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

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


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    n, m, s, t = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(m)]  # int grid

    yen_neighbour_mat = np.zeros((n, n))
    snuuke_neighbour_mat = np.zeros((n, n))

    for u, v, yen, snuuke in grid:
        u = u - 1
        v = v - 1
        yen_neighbour_mat[u, v] = yen_neighbour_mat[v, u] = yen
        snuuke_neighbour_mat[u, v] = snuuke_neighbour_mat[v, u] = snuuke

    yen_csr = csr_matrix(yen_neighbour_mat)
    sn_csr = csr_matrix(snuuke_neighbour_mat)

    min_dist_list = []
    result_list = []
    for i_year in reversed(range(n)):

        min_dist_list.append(
            dijkstra(yen_csr, directed=False, indices=i_year)[s - 1] +
            dijkstra(sn_csr, directed=False, indices=i_year)[t - 1])

        result_list.append(min(min_dist_list))

    for r in reversed(result_list):
        print(int(10**15) - int(r))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1"""
        output = """999999999999998
999999999999989
999999999999979
999999999999897"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994"""
        self.assertIO(input, output)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.INFO)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

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


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    n, m, s, t = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(m)]  # int grid

    yen_neighbour_mat = np.zeros((n, n))
    snuuke_neighbour_mat = np.zeros((n, n))

    for u, v, yen, snuuke in grid:
        u = u - 1
        v = v - 1
        yen_neighbour_mat[u, v] = yen_neighbour_mat[v, u] = yen
        snuuke_neighbour_mat[u, v] = snuuke_neighbour_mat[v, u] = snuuke

    yen_csr = csr_matrix(yen_neighbour_mat)
    sn_csr = csr_matrix(snuuke_neighbour_mat)

    logger.debug('{}'.format([
        yen_neighbour_mat,
        dijkstra(yen_csr, directed=False, indices=[t - 1])
    ]))

    min_dist_list = []
    result_list = []
    for i_year in reversed(range(n)):
        logger.debug('{}'.format([
            i_year,
            dijkstra(yen_csr, directed=False, indices=i_year)[s - 1],
            dijkstra(sn_csr, directed=False, indices=i_year)[t - 1]
        ]))
        min_dist_list.append(
            dijkstra(yen_csr, directed=False, indices=i_year)[s - 1] +
            dijkstra(sn_csr, directed=False, indices=i_year)[t - 1])

        result_list.append(min(min_dist_list))

        logger.debug('{}'.format([min_dist_list, result_list]))

    for r in reversed(result_list):
        print(int(10**15) - int(r))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1"""
        output = """999999999999998
999999999999989
999999999999979
999999999999897"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994"""
        self.assertIO(input, output)

Submission status: Runtime Error

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

    import numpy as np
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, c]) for u, v, c in abc]
    [g[i+1].append([i, 0]) for i in range(n-1)]

    import heapq

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


main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = np.append(uvab[:, 2], uvab[:, 2])
    row = np.append(uvab[:, 0], uvab[:, 1]) - 1
    col = np.append(uvab[:, 1], uvab[:, 0]) - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    yen = sp.csgraph.shortest_path(matrix, indices=s-1)

    data = np.append(uvab[:, 3], uvab[:, 3])
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    snk = sp.csgraph.shortest_path(matrix, indices=t-1)

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

    cost = 10**15-cost

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


main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = uvab[:, 2]
    row = uvab[:, 0] - 1
    col = uvab[:, 1] - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.shortest_path(matrix, indices=s-1, directed=False)

    data = uvab[:, 3]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.shortest_path(matrix, indices=t-1, directed=False)

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

    cost = 10**15-cost

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


main()

Submission status: Runtime Error

Solution code:
import heapq, sys
def input():
    return sys.stdin.readline()[:-1]

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

yen_edge = [[] for _ in range(n)]
snuke_edge = [[] for _ in range(n)]

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

class DijkstraList():
    #隣接リスト版
    def __init__(self, adj, start):
        self.list = adj
        self.start = start
        self.size = len(adj)

    def solve(self):
        self.dist = [float("inf") for _ in range(self.size)]
        self.dist[self.start] = 0
        self.q = []

        heapq.heappush(self.q, self.start)

        while self.q:
            u = heapq.heappop(self.q)
            u_dist = self.dist[u]
            for v, w in self.list[u]:
                if self.dist[v] > u_dist + w:
                    self.dist[v] = u_dist + w
                    heapq.heappush(self.q, v)

            self.cnt += 1

        return

    def distance(self, goal):
        return self.dist[goal]

yen = DijkstraList(yen_edge, s - 1)
snuke = DijkstraList(snuke_edge, t - 1)
yen.solve()
snuke.solve()
ans_list = []

for i in range(n):
	ans_list.append(yen.distance(i) + snuke.distance(i))

ans = []

ans.append(10 ** 15 - ans_list[n - 1])

for i in range(1, n):
	if ans_list[n - i - 1] > ans_list[n - i]:
		ans_list[n - i - 1] = ans_list[n - i]
	ans.append(10 ** 15 - ans_list[n - i - 1])

for i in range(n - 1, -1, -1):
	print(ans[i])

Submission status: Runtime Error

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

n, m, s, t = map(int, input().split())
moni = 10**15
graph_y = [[-1 for _ in range(n)] for _ in range(n)]
graph_s = [[-1 for _ in range(n)] for _ in range(n)]

for i in range(m):
	u, v, a, b = map(int, input().split())
	graph_y[u-1][v-1] = a
	graph_s[u-1][v-1] = b

op_y = dijkstra(csgraph_from_dense(graph_y, null_value=-1), directed=False)
op_s = dijkstra(csgraph_from_dense(graph_s, null_value=-1), directed=False)

l = [float("inf") for _ in range(n)]
l[n-1] = int(op_y[s-1][n-1] + op_s[t-1][n-1])
for i in range(n-2, -1, -1):
	k = int(op_y[s-1][i] + op_s[t-1][i])
	if k < l[i+1]:
		l[i] = k
	else:
		l[i] = l[i+1]

for i in range(n):
	print(moni - l[i])

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
n,m,s,t=map(int,input().split())

E=[[10**15 for j in range(n+1)]for i in range(n+1)]
S=[[10**15 for j in range(n+1)]for i in range(n+1)]

for i in range(m):
    x,y,a,b=map(int,input().split())
    E[x][y]=a
    E[y][x]=a
    S[x][y]=b
    S[y][x]=b
    
#print(E)
#print(S)
E=dijkstra(E,indices = s)
S=dijkstra(S,indices = t)
#print(E)
#print(S)

Q=[]
for i in range(1,n+1):
    Q.append((int(E[i]+S[i]),i))

Q.sort()
cnt=0
for i in range(1,n+1):
    while Q[cnt][1]<i:
        cnt+=1
    print(10**15-Q[cnt][0])
#print(Q)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
n,m,s,t=map(int,input().split())

E=[[10**15 for j in range(n+1)]for i in range(n+1)]
S=[[10**15 for j in range(n+1)]for i in range(n+1)]

for i in range(m):
    x,y,a,b=map(int,input().split())
    E[x][y]=a
    E[y][x]=a
    S[x][y]=b
    S[y][x]=b
    
#print(E)
#print(S)
E=dijkstra(E,indices = s)
S=dijkstra(S,indices = t)
#print(E)
#print(S)

Q=[]
for i in range(1,n+1):
    Q.append((int(E[i]+S[i]),i))

import heapq
heapq.heapify(Q)
for i in range(1,n+1):
    while Q[0][1]<i:
        heapq.heappop(Q)
    print(10**15-Q[0][0])

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("INF")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

Submission status: Runtime Error

Solution code:
from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p,g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+i
                heappush(q,[p[i],i])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

Submission status: Runtime Error

Solution code:
from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p,g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i in r[z]:
            if p[i[0]]>y+i[1]:
                p[i[0]]=y+i[0]
                heappush(q,[y+i[1],i[0]])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append([s1[i]+t1[i],i])
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

Submission status: Runtime Error

Solution code:
from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p.g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i in r[z]:
            if p[i[0]]>y+i[1]:
                heappush(q,[y+i[1],i[0]])
    return p
s1,t1=f(s,a),f(t,b)
q=np.array(s1[1:])+np.array(t1[1:])
q=q.tolist()
for i in range(n):
    print(10**15-min(q))
    q=q[1:]

Submission status: Runtime Error

Solution code:
from collections import deque
n,m,s,t = map(int,input().split())
edgem = [[]for i in range(n)]
edges = [[]for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgem[u-1].append([v-1,a])
    edgem[v-1].append([u-1,a])
    edges[u-1].append([v-1,b])
    edges[v-1].append([u-1,b])

costm = [float('inf')]*n
costs = [float('inf')]*n
costm[s-1],costs[t-1] = 0,0

queue = deque([s-1])
while queue != deque([]) > 0:
    p = queue.popleft()
    for a,b in edgem[p]:
        if costm[a] > costm[p] + b:
            costm[a] = costm[p] + b
            queue.append(a)
queue = deque([t-1])
while queue != deque([]):
    p = queue.popleft()
    for a,b in edges[p]:
        if costs[a] > costs[p] + b:
            costs[a] = costs[p] + b
            queue.append(a)
ans = [float('inf')]*n
for i in range(n):
    ans[i] = costm[i] + costs[i]
for i in range(n-1,0,-1):
    ans[i-1] = min(ans[i-1],ans[i])
money = 10**15
for i in ans:
    print(money-i)

Submission status: Runtime Error

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

c = []
for i in range(m):
  c.append([u[i]-1,v[i]-1,a[i]])
  c.append([v[i]-1,u[i]-1,a[i]])

from heapq import heappop, heappush
inf=float('inf')
d=[inf for _ in range(n)]
d[s-1]=0
prev=[None]*n
p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[s-1],s-1))
while q:
  du, u1 = heappop(q)
  if d[u1]<du: continue
  for v1,weight in p.get(u1,[]):
    alt=du+weight
    if d[v1]>alt:
      d[v1]=alt
      prev[v1]=u1
      heappush(q, (alt,v1))

c2 = []
for i in range(m):
  c2.append([u[i]-1,v[i]-1,b[i]])
  c2.append([v[i]-1,u[i]-1,b[i]])

d2=[inf for _ in range(n)]
d2[t-1]=0
prev=[None]*n
p=dict()
for i,j,k in c2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d2[t-1],t-1))
while q:
  du, u2 = heappop(q)
  if d2[u2]<du: continue
  for v2,weight in p.get(u2,[]):
    alt=du+weight
    if d2[v2]>alt:
      d2[v2]=alt
      prev[v2]=u2
      heappush(q, (alt,v2))

ans = d[n-1]+d2[n-1]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

long long src[100001], tgt[100001];

vector<pair<int, pair<int, int>>> adj[100001];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    for(int i = 0; i < n; ++i)
        src[i] = tgt[i] = 100000000000000LL;

    for(int i = 0; i < m; ++i){
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        --x; --y;
        adj[x].push_back(make_pair(y, make_pair(a, b))); adj[y].push_back(make_pair(x, make_pair(a, b)));
    }

    // Source

    priority_queue<pair<long long, int>> q;
    q.push(make_pair(0, s - 1));

    while(!q.empty()){
        pair<long long, int> state = q.top();
        q.pop();
        long long cost = -state.first;
        int node = state.second;
        if(cost >= src[node])
            continue;
        src[node] = cost;
        for(auto nx : adj[node]){
            if(cost + nx.second.first >= src[nx.first])
                continue;
            q.push(make_pair(-(cost + nx.second.first), nx.first));
        }
    }

    q.push(make_pair(0, t - 1));

    while(!q.empty()){
        pair<long long, int> state = q.top();
        q.pop();
        long long cost = -state.first;
        int node = state.second;
        if(cost >= tgt[node])
            continue;
        tgt[node] = cost;
        for(auto nx : adj[node]){
            if(cost + nx.second.second >= tgt[nx.first])
                continue;
            q.push(make_pair(-(cost + nx.second.second), nx.first));
        }
    }

    priority_queue<pair<long long, int>> best;

    for(int i = 0; i < n; ++i){
        best.push(make_pair(-(src[i] + tgt[i]), i)); // cost, year it closes
    }

    for(int i = 0; i < n; ++i){ // year we start
        while(best.top().second < i)
            best.pop();
        cout << 1000000000000000LL + best.top().first << "\n";
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heapq.heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heapq.heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                if distance[v] > k + d:
                    distance[v] = k + d
                    heapq.heappush(queue, (k + d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10 ** 15 - ans_list[-(i + 1)])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heapq.heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heapq.heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                if distance[v] > k + d:
                    distance[v] = k + d
                    heapq.heappush(queue, (k + d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10 ** 15 - ans_list[-(i + 1)])