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: Time Limit Exceeded

Solution code:
import numpy as np
INF = 10**20

n,m,s,t = map(int,input().split())
u = np.zeros(m)
v = np.zeros(m)
a = np.zeros(m)
b = np.zeros(m)

i = 0
while(i < m):
    u[i],v[i],a[i],b[i] = map(int,input().split())
    i += 1

#s to i
dist = np.ones(n)*INF
dist[s-1] = 0
Q1 = np.arange(n).reshape((1,n))
Q2 = np.zeros(n).reshape((1,n))
Q = np.concatenate((Q1,Q2),axis=0)

while(np.sum(Q[1,:] == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    sorted_Q = Q[:,dist_argsorted]
    dijk_u = int(sorted_Q[0,np.argmax(sorted_Q[1])])
    Q[1,dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)],v[np.where(u == dijk_u + 1)]),axis=0) -1)
    #print(queue)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1)[0],np.where(v == big+1)[0])[0]
        #print(row)
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + a[raw]):
            dist[dijk_v] = dist[dijk_u] + a[raw]


yens = dist.copy()

#t to i
dist = np.ones(n)*INF
dist[t-1] = 0
Q1 = np.arange(n).reshape((1,n))
Q2 = np.zeros(n).reshape((1,n))
Q = np.concatenate((Q1,Q2),axis=0)

while(np.sum(Q[1,:] == -1) < n):
    dist_argsorted = np.argsort(dist)
    sorted_Q = Q[:,dist_argsorted]
    dijk_u = int(sorted_Q[0,np.argmax(sorted_Q[1])])
    Q[1,dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)], v[np.where(u == dijk_u + 1)]), axis=0) - 1)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1)[0],np.where(v == big+1)[0])[0]
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + b[raw]):
            dist[dijk_v] = dist[dijk_u] + b[raw]

snuuks = dist.copy()

total_costs = yens + snuuks
#print(yens)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
INF = 10**20

n,m,s,t = map(int,input().split())
u = np.zeros(m)
v = np.zeros(m)
a = np.zeros(m)
b = np.zeros(m)

i = 0
while(i < m):
    u[i],v[i],a[i],b[i] = map(int,input().split())
    i += 1

#s to i
dist = np.ones(n)*INF
dist[s-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while(1):
        dijk_u = dist_argsorted[i]
        i += 1
        if(Q[dijk_u] != -1):
            break

    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)],v[np.where(u == dijk_u + 1)]),axis=0) -1)
    #print(queue)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1)[0],np.where(v == big+1)[0])[0]
        #print(row)
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + a[raw]):
            dist[dijk_v] = dist[dijk_u] + a[raw]
            prev[dijk_v] = dijk_u


yens = dist.copy()

#t to i
dist = np.ones(n)*INF
dist[t-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while (1):
        dijk_u = dist_argsorted[i]
        i += 1
        if (Q[dijk_u] != -1):
            break
    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)], v[np.where(u == dijk_u + 1)]), axis=0) - 1)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1)[0],np.where(v == big+1)[0])[0]
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + b[raw]):
            dist[dijk_v] = dist[dijk_u] + b[raw]
            prev[dijk_v] = dijk_u

snuuks = dist.copy()

total_costs = yens + snuuks
#print(yens)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
roots = defaultdict(set)

#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #

	roots[u].add((v,a,b))
	roots[v].add((u,a,b))
		
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global weight_yen
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[1]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global weight_snu
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[2]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_snu[i] = w

#q = 次に探索する(確定する)もの q[0]=[w,n]
q = [[0,s]]
heapq.heapify(q)
			
while q:
	w,n = heapq.heappop(q)
	search_yen(n,w)
	
heapq.heappush(q, [0,t])
	
while q:
	w,n = heapq.heappop(q)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
root_yen = defaultdict(set)
root_snu = defaultdict(set)


#cost[a][b] = a -> b のコスト
cost_yen = [[0 for i in range(N+1)] for j in range(N+1)]
cost_snu = [[0 for i in range(N+1)] for j in range(N+1)]


#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


#q = 次に探索する(確定する)もの q[0]=[w,n]
q_yen = [[0,s]]
q_snu = [[0,t]]
heapq.heapify(q_yen)
heapq.heapify(q_snu)


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #
	
	root_yen[u].add(v)
	root_yen[v].add(u)
	
	root_snu[u].add(v)
	root_snu[v].add(u)
	
	cost_yen[u][v] = a
	cost_yen[v][u] = a
	cost_snu[u][v] = b
	cost_snu[v][u] = b
	
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global cost_yen
	global weight_yen
	global q_yen
		
	for i in list(root_yen[n]):
		w = w_0 + cost_yen[n][i]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q_yen, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global cost_snu
	global weight_snu
	global q_snu
		
	for i in list(root_snu[n]):
		w = w_0 + cost_snu[n][i]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q_snu, [w,i])
			weight_snu[i] = w			
			
while q_yen:
	w,n = heapq.heappop(q_yen)
	search_yen(n,w)
	
while q_snu:
	w,n = heapq.heappop(q_snu)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        """
        if D[site - 1] > cost:
            D[site - 1] = cost
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
        """
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in graph[u].items():
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [dict() for _ in range(n)]
snuke_graph = [dict() for _ in range(n)]

for line in sys.stdin.readlines():
    u, v, a, b = map(int, line.strip().split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in graph[u].items():
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [dict() for _ in range(n)]
snuke_graph = [dict() for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import accumulate
import heapq
n,m,s,t=map(int, input().split())
s-=1
t-=1
yen=[[0 for _ in range(n)] for _ in range(n)]
snk=[[0 for _ in range(n)] for _ in range(n)]
adj=defaultdict(list)
for _ in range(m):
    u,v,a,b=map(int, input().split())
    u-=1    
    v-=1    
    adj[u].append(v)
    adj[v].append(u)
    yen[u][v]=a
    yen[v][u]=a
    snk[u][v]=b
    snk[v][u]=b

def dijkstra(s, t, cost):
    q=[]
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(q, (d[s], s))
    while q!=[]:
        du, u=heapq.heappop(q)
        if du>d[u]:
            continue
        for v in adj[u]:
            tmp=du+cost[u][v]
            if d[v]>tmp:
                d[v]=tmp
                heapq.heappush(q, (d[v], v))
    return d

d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
snuke=[]
for d1i, d2i in zip(d1,d2):
    snuke.append(d1i+d2i)
ans=list(accumulate(reversed([y+s for y,s in zip(d1, d2)]), min))
for ai in reversed(ans):
    print(10**15-ai)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s)
snuke = min_cost(root2, t)
cost = [jpy[i] + snuke[i] for i in range(n)]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(root, x):
    return([(b, root[(a, b)]) for (a, b) in root if a == x] + [(a, root[(a, b)]) for (a, b) in root if b == x])

root1 = [edge(root1, i + 1) for i in range(n)]
root2 = [edge(root2, i + 1) for i in range(n)]

def min_cost(root, start):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in root[site - 1]:
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s)
snuke = min_cost(root2, t)
cost = [jpy[i] + snuke[i] for i in range(n)]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in edge(G, site):
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s)
snuke = min_cost(root2, t)
cost = [jpy[i] + snuke[i] for i in range(n)]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start, end):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in edge(G, site):
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D[end - 1]

cost = []
for i in range(n):
    cost.append(min_cost(root1, s, i + 1) + min_cost(root2, i + 1, t))

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

Submission status: Time Limit Exceeded

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start, end):
    S = {start: 0}
    D = {}
    while len(S) > 0:
        x = select_min(S)
        m = S[x]
        del S[x]
        D[x] = m
        for (y, w) in edge(G, x):
            if y in S:
                if S[y] > m + w:
                    S[y] = m + w
            elif y not in D:
                S[y] = m + w
    return D[end]

def select_min(S):
    m = -1
    for a in S:
        if m == -1 or m > S[a]:
            x = a
            m = S[a]
    return x

cost = []
for i in range(n):
    cost.append(min_cost(root1, s, i + 1) + min_cost(root2, i + 1, t))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

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

money = defaultdict(set)
snuke = defaultdict(set)
for i in range(m):
    a, b, c, d = map(int, input().split())
    money[a-1].add((b-1, c))
    money[b-1].add((a-1, c))
    snuke[a-1].add((b-1, d))
    snuke[b-1].add((a-1, d))

def dijkstra(n, v, dedic):
    d = [float('inf')] * n
    d[v] = 0

    hq = [(0, v)]

    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in dedic[u]:
            if d[nv] > d[u] + c:
                d[nv] = d[u] + c
                heapq.heappush(hq, (d[u] + c, nv))

    return d

money_cost = dijkstra(n, s - 1, money)
snuke_cost = dijkstra(n, t - 1, snuke)

result = [10 ** 15 for _ in range(n)]
for i in range(n):
    result[i] -= money_cost[i] + snuke_cost[i]

for i in range(n):
    print(max(result[i:]))

Submission status: Time Limit Exceeded

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

V=10**15
ans=[0]*n
from heapq import heappush,heappop
def dijkstra(u,k):
    D=[10**18]*n
    q=[(u,0)]
    D[u]=0
    while q:
        u,d=heappop(q)
        if D[u]<d: continue
        for v ,a ,b in G[u]:
            w=b if k else a
            if d + w < D[v]:
                D[v]=d+w
                heappush(q,(v,d+w))
    return D
D1=dijkstra(s,0)
D2=dijkstra(t,1)
tmp=1e18
for i in reversed(range(n)):
    tmp=min(tmp,D1[i]+D2[i])
    ans[i]=10**15-tmp
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import heapq

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    for year in range(n):
        cost = min(total[year:])
        print(money - cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    for year in range(n):
        for i in range(year, n):
            cost = min(total[year:])

        print(money - cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

def memo(G, n, s):
    cost = list()
    for i in range(n):
        cost.append(shortest_path(G, s, i))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for i in range(n)] # JPY
    H = [{} for i in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = memo(G, n, S)
    min_snk = memo(H, n, T)
    for year in range(n):
        cost = None
        for i in range(year, n):
            t = min_jpy[i] + min_snk[i]
            if cost is None:
                cost = t
            else:
                if cost > t:
                    cost = t

        print(money - cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

Submission status: Time Limit Exceeded

Solution code:
import queue

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

def shortest_path(G, s, t):
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0,s))

    while q.empty() == False:
        w,x = q.get()
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                q.put((w + G[x][y], y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    d = [inf for j in range(num_v)]
    l = [[] for i in range(n)]
    for pi in edge:  
      l[pi[0]].append(pi[1])
      l[pi[1]].append(pi[0])
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest in l[src]:
        you = cost[src][dest]
        if you != float('inf') and d[dest] > d[src] + you:
          d[dest] = d[src] + you
          heapq.heappush(q, (d[dest], dest))
    return d


from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    syou = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if prov_cost > syou:
        break
      if d[src] < prov_cost:
                continue
      for dest in range(num_v):
        you = cost[src][dest]
        if you != float('inf') and d[dest] > d[src] + you:
          d[dest] = d[src] + you
          heapq.heappush(q, (d[dest], dest))
          syou = max(d[dest],syou)
    return d


from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])