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 numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.zeros((n, n), dtype=int)
links_cost_sn = np.zeros((n, n), dtype=int)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - int(ans[i]))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), 10**9, dtype=int)
links_cost_sn = np.full((n, n), 10**9, dtype=int)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - int(ans[i]))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial, dtype=int)
links_cost_sn = np.full((n, n), initial, dtype=int)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - int(ans[i]))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial)
links_cost_sn = np.full((n, n), initial)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - int(ans[i]))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = np.full(n, initial)
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial)
links_cost_sn = np.full((n, n), initial)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = np.full(n, initial)
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

Submission status: Runtime Error

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

if d == 0:
    print((m-1) / n)
else:
    print((m-1) * 2 * (n - d) / n ** 2)

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = np.full(n, initial_cost)
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = int(heapq.heappop(node_list) % dif)
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial_cost)
links_cost_sn = np.full((n, n), initial_cost)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = np.full(n, initial_cost)
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = np.full(n, initial_cost)
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = int(heapq.heappop(node_list) % dif)
        if index in serched_node:
            continue
        serched_node.add(index)
        
        print(index)
        print(links)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial_cost)
links_cost_sn = np.full((n, n), initial_cost)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = np.full(n, initial_cost)
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, s, t = map(int, input().split())
uvab = []
for i in range(m):
    uvab.append(list(map(int,input().split())))
Ga = np.zeros((n,n))
Gb = np.zeros((n,n))

for i in range(m):
    Ga[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][2])
    Ga[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][2])
    Gb[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][3])
    Gb[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][3])


def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 1000000000000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost

    
Gacost = search(Ga, s-1, t-1)
Gbcost = search(Gb, t-1, s-1)

sumG = [x + y for (x, y) in zip(Gacost, Gbcost)]


for i in range(n):
    print(1000000000000000-int(min(sumG[i:])))

Submission status: Runtime Error

Solution code:
import heapq
 
def dijkstra(s, G):
    que = [(0, s)]
    d = [float("inf")]*len(G)
    d[s] = 0
    while que:
        c, v = heapq.heappop(que)
        if d[v] > c: continue
        for to, cost in G[v]:
            if d[to] > d[v] + cost:
                d[to] = d[v] + cost
                heapq.heappush(que, (d[to], to))
    return d
 
n, m, s, t = map(int, raw_input().split())
s, t = s - 1, t - 1 
G0, G1 = [[] for i in xrange(n)], [[] for i in xrange(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, raw_input().split())
    ui, vi = ui - 1, vi - 1
    G0[ui].append((vi, ai))
    G0[vi].append((ui, ai))
    G1[ui].append((vi, bi))
    G1[vi].append((ui, bi))
 
d0 = dijkstra(s, G0)
d1 = dijkstra(t, G1)
 
yen = 10**15
ans = [float("inf")]*(n + 1)
for i in xrange(n - 1, -1, -1):
    ans[i] = min(ans[i + 1], d0[i] + d1[i])
 
for i in xrange(n):
    print yen - ans[i]

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, s, t = map(int, input().split())
uvab = []
for i in range(m):
    uvab.append(list(map(int,input().split())))
Ga = np.zeros((n,n))
Gb = np.zeros((n,n))

for i in range(m):
    Ga[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][2])
    Ga[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][2])
    Gb[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][3])
    Gb[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][3])



def print_path(prev, cost):
    Gcost = []
    for i in range(len(prev)):
        #print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))
        Gcost.append(cost[i])
    return Gcost

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 1000000000000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    Gcost = print_path(prev, cost)
    #return [get_path(start, goal, prev), cost[goal]]
    return Gcost

    
Gacost = search(Ga, s-1, 1)
Gbcost = search(Gb, t-1, 1)
#print(Gacost+Gbcost)
sumG = [x + y for (x, y) in zip(Gacost, Gbcost)]
#print(sumG)
#print(path, 'cost: ', cost)

for i in range(n):
    print(1000000000000000-int(min(sumG[i:])))

Submission status: Runtime Error

Solution code:
import networkx as nx

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

Graph1=nx.DiGraph()
Graph2=nx.DiGraph()

for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    Graph1.add_weighted_edges_from([(u-1,v-1,a),(v-1,u-1,a)])
    Graph2.add_weighted_edges_from([(u-1,v-1,b),(v-1,u-1,b)])

dp=[10**9 for i in range(n)]
for i in range(n):
    dp[i]=nx.dijkstra_path_length(Graph1,s,i)+nx.dijkstra_path_length(Graph2,i,t)

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

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, s, t = map(int, input().split())
uvab = []
for i in range(m):
    uvab.append(list(map(int,input().split())))
Ga = np.zeros((n,n))
Gb = np.zeros((n,n))

for i in range(m):
    Ga[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][2])
    Ga[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][2])
    Gb[uvab[i][0]-1][uvab[i][1]-1]=int(uvab[i][3])
    Gb[uvab[i][1]-1][uvab[i][0]-1]=int(uvab[i][3])



def print_path(prev, cost):
    Gcost = []
    for i in range(len(prev)):
        #print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))
        Gcost.append(cost[i])
    return Gcost

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    Gcost = print_path(prev, cost)
    #return [get_path(start, goal, prev), cost[goal]]
    return Gcost

    
Gacost = search(Ga, s-1, 1)
Gbcost = search(Gb, t-1, 1)
#print(Gacost+Gbcost)
sumG = [x + y for (x, y) in zip(Gacost, Gbcost)]
#print(sumG)
#print(path, 'cost: ', cost)

for i in range(n):
    print(1000000000000000-int(min(sumG[i:])))

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    n_station, n_train, src_station, dst_station = [int(_) for _ in input().split()]

    connect = []
    for _ in range(n_station + 1):
        connect.append([])

    trains = {}
    for _ in range(n_train):
        u, v, a, b = [int(_) for _ in input().split()]
        trains[str(u) + str(v)] = {
            "yen": a,
            "snk": b
        }
        connect[u].append(v)
        connect[v].append(u)

    costs_by_exchange_station = [10**20]

    stat_and_cost_arr = [(src_station, 0)]
    costs_yen = {src_station: 0}
    while True:
        new_stat_and_cost_arr = []
        for stat_and_cost in stat_and_cost_arr:
            new_stat_and_cost_arr = []
            current_station, current_cost = stat_and_cost[0], stat_and_cost[1]

            for next_station in connect[current_station]:
                u, v = min(current_station, next_station), max(current_station, next_station)
                if next_station not in costs_yen or current_cost + trains[str(u) + str(v)]["yen"] < costs_yen[next_station]:
                    new_stat_and_cost_arr.append((next_station, current_cost + trains[str(u) + str(v)]["yen"]))
                    costs_yen[next_station] = current_cost + trains[str(u) + str(v)]["yen"]

        if len(new_stat_and_cost_arr) == 0:
            break
        else:
            stat_and_cost_arr = new_stat_and_cost_arr

    for exchange_station in range(1, n_station + 1):
        stat_and_cost_arr = [(exchange_station, costs_yen[exchange_station])]

        costs_snk = {exchange_station: costs_yen[exchange_station]}
        while True:
            new_stat_and_cost_arr = []
            for stat_and_cost in stat_and_cost_arr:
                new_stat_and_cost_arr = []
                current_station, current_cost = stat_and_cost[0], stat_and_cost[1]

                for next_station in connect[current_station]:
                    u, v = min(current_station, next_station), max(current_station, next_station)
                    if next_station not in costs_snk or current_cost + trains[str(u) + str(v)]["snk"] < costs_snk[next_station]:
                        new_stat_and_cost_arr.append((next_station, current_cost + trains[str(u) + str(v)]["snk"]))
                        costs_snk[next_station] = current_cost + trains[str(u) + str(v)]["snk"]

            if len(new_stat_and_cost_arr) == 0:
                break
            else:
                stat_and_cost_arr = new_stat_and_cost_arr

        costs_by_exchange_station.append(costs_snk[dst_station])

    for year in range(n_station):
        print(10**15 - min(costs_by_exchange_station[year+1:]))




main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    n_station, n_train, src_station, dst_station = [int(_) for _ in input().split()]

    connect = []
    for _ in range(n_station + 1):
        connect.append([])

    trains = {}
    for _ in range(n_train):
        u, v, a, b = [int(_) for _ in input().split()]
        trains[str(u) + str(v)] = {
            "yen": a,
            "snk": b
        }
        connect[u].append(v)
        connect[v].append(u)

    costs_by_exchange_station = [10**20]

    stat_and_cost_arr = [(src_station, 0)]
    costs_yen = {src_station: 0}
    while True:
        new_stat_and_cost_arr = []
        for stat_and_cost in stat_and_cost_arr:
            new_stat_and_cost_arr = []
            current_station, current_cost = stat_and_cost[0], stat_and_cost[1]

            for next_station in connect[current_station]:
                u, v = min(current_station, next_station), max(current_station, next_station)
                if costs_yen.get(next_station, -1) == -1 or current_cost + trains[str(u) + str(v)]["yen"] < costs_yen[next_station]:
                    new_stat_and_cost_arr.append((next_station, current_cost + trains[str(u) + str(v)]["yen"]))
                    costs_yen[next_station] = current_cost + trains[str(u) + str(v)]["yen"]

        if len(new_stat_and_cost_arr) == 0:
            break
        else:
            stat_and_cost_arr = new_stat_and_cost_arr

    for exchange_station in range(1, n_station + 1):
        stat_and_cost_arr = [(exchange_station, costs_yen[exchange_station])]

        costs_snk = {exchange_station: costs_yen[exchange_station]}
        while True:
            new_stat_and_cost_arr = []
            for stat_and_cost in stat_and_cost_arr:
                new_stat_and_cost_arr = []
                current_station, current_cost = stat_and_cost[0], stat_and_cost[1]

                for next_station in connect[current_station]:
                    u, v = min(current_station, next_station), max(current_station, next_station)
                    if costs_snk.get(next_station, -1) == -1 or current_cost + trains[str(u) + str(v)]["snk"] < costs_snk[next_station]:
                        new_stat_and_cost_arr.append((next_station, current_cost + trains[str(u) + str(v)]["snk"]))
                        costs_snk[next_station] = current_cost + trains[str(u) + str(v)]["snk"]

            if len(new_stat_and_cost_arr) == 0:
                break
            else:
                stat_and_cost_arr = new_stat_and_cost_arr

        costs_by_exchange_station.append(costs_snk[dst_station])

    for year in range(n_station):
        print(10**15 - min(costs_by_exchange_station[year+1:]))




main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heapify, heappop

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

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
        #for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]



def dijkstra2(graph, source):
    inf = float('inf')
    dist = defaultdict(lambda: inf)
    previous = {}
    visited = set()

    dist[source] = 0
    graph_nodes = [(dist[n], n) for n in graph.keys()]
    heapify(graph_nodes)
    while graph_nodes:
        _, u = heappop(graph_nodes)
        visited.add(u)
        if dist[u] == inf:
            break

        for v in graph[u]:
            if v in visited:
                continue
            alt = dist[u] + graph[u][v]
            if alt < dist[v]:
                i = graph_nodes.index((dist[v], v))
                graph_nodes[i] = (alt, v)
                heapify(graph_nodes)

                dist[v] = alt
                previous[v] = u

    return dist


#jpy_dijk = (dijkstra(jpy_cost,s-1,s-1,n))
#snuke_dijk = (dijkstra(snuke_cost,t-1,t-1,n))
jpy_dijk = (dijkstra2(jpy_cost,s-1))
raise
snuke_dijk = (dijkstra2(snuke_cost,t-1))
raise

#print(s,t)
#print(jpy_dijk)
#print(snuke_dijk)
#print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)