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 sys

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen, d_snuuk)]
    print(10**15 - min(cost_sum))
    del d_yen[0]
    del d_snuuk[0]

Submission status: Time Limit Exceeded

Solution code:
import sys

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen[i:], d_snuuk[i:])]
    print(10**15 - min(cost_sum))

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen[i:], d_snuuk[i:])]
    print(10**15 - min(cost_sum))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from queue import PriorityQueue as PQ

def pcc(src, adj):
	pq = PQ()
	pq.put((0,src))
	dist = [float('inf')]*n
	dist[src] = 0
	while not pq.empty():
		d, u = pq.get()
		# ~ print(d,u)
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put((dist[v], v))
	return dist

n,m,s,t = map(int,input().split())
s,t = s-1,t-1
adjs = [[] for _ in range(n)]
adjt = [[] for _ in range(n)]
for _ in range(m):
	u,v,a,b = map(int, input().split())
	u,v = u-1,v-1
	adjs[u].append((a,v))
	adjs[v].append((a,u))
	adjt[u].append((b,v))
	adjt[v].append((b,u))

dist_s = pcc(s, adjs)
dist_t = pcc(t, adjt)

ans = [0]*n
ans[n-1] = 10**15 - dist_s[n-1]-dist_t[n-1]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], 10**15 - dist_s[i] - dist_t[i])
print(*ans, sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for _ in range(n+1)]
adjt = [[] for _ in range(n+1)]
for _ in range(m):
	u,v,a,b = map(int, input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
ans = [0]*(n)
ans[n-1] = yen -dist_s[n] - dist_t[n]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i+1] - dist_t[i+1])
print(*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for _ in range(n+1)]
adjt = [[] for _ in range(n+1)]
for _ in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
# ~ ans = [0]*(n)
# ~ ans[n-1] = yen -dist_s[n] - dist_t[n]
# ~ for i in range(n-2,-1,-1):
	# ~ ans[i] = max(ans[i+1], yen - dist_s[i+1] - dist_t[i+1])
# ~ print(*ans, sep = '\n')
ans = [-1] * n
tmp = float('inf')
for i in range(n, 0, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i-1] = 10 ** 15 - tmp
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for _ in range(n+1)]
adjt = [[] for _ in range(n+1)]
for _ in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
ans = [0]*(n)
ans[n-1] = yen -dist_s[n] - dist_t[n]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i+1] - dist_t[i+1])
print(*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for i in range(n+1)]
adjt = [[] for i in range(n+1)]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

ans = [0]*(n+1)
ans[n] = yen -dist_s[n] - dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i] - dist_t[i])
print(*ans[1:], sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for i in range(n+1)]
adjt = [[] for i in range(n+1)]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

ans = [0]*(n+1)
ans[n] = yen -dist_s[n] - dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i] - dist_t[i])
print(*ans[1:], sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = []
adjt = []
for i in range(n+1):
	adjs += [[]]
	adjt += [[]]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)



ans = [0]*(n+1)
ans[n] = dist_s[n] + dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], dist_s[i] + dist_t[i])
for i in range(1,n+1):
	print(yen-ans[i])

Submission status: Time Limit Exceeded

Solution code:
from queue import PriorityQueue as PQ

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = PQ()
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put([dist[v], v])
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = []
adjt = []
for i in range(n+1):
	adjs += [[]]
	adjt += [[]]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)



ans = [0]*(n+1)
ans[n] = dist_s[n] + dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], dist_s[i] + dist_t[i])
for i in range(1,n+1):
	print(yen-ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 17
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [INF] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [INF] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i + 1] + snu[i + 1],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [0] * n
for i in range(n):
    cost[i] = [yen[i + 1] + snu[i + 1],i]

heapq.heapify(cost)
c = -1
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(10 ** 15 - nn)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [[float("INF"),float("INF")]] * (n + 1)
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

cost.sort(key = lambda x: x[0])

nn = -1
l = 0
for i in range(1, n + 1):
    if nn < i:
        for j in range(l, len(cost)):
            if cost[j][1] >= i:
                ss = cost[j][0]
                nn = cost[j][1]
                l = j + 1
                break
    print(10**15-ss)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

cost.sort(key = lambda x: x[0])

nn = -1
for i in range(1, n + 1):
    if nn < i:
        for j in cost:
            if j[1] >= i:
                ss = j[0]
                nn = j[1]
                break
    print(10**15-ss)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

cost.sort(key = lambda x: x[0])

for i in range(1, n + 1):
    for j in cost:
        if j[1] >= i:
            print(1000000000000000 - j[0])
            break

Submission status: Time Limit Exceeded

Solution code:
from queue import PriorityQueue as PQ

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = PQ()
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put([dist[v], v])
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = []
adjt = []
for i in range(n+1):
	adjs += [[]]
	adjt += [[]]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

tab = [0]*(n+1)
for i in range(1,n+1):
	tab[i] = dist_s[i] + dist_t[i]
	# ~ print("echange",i," = ",tab[i])
	# ~ tab[i] = yen - tab[i]

ans = [0]*(n+1)
ans[n] = tab[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], tab[i])
	
for i in range(n):
	print(yen - ans[i+1])

Submission status: Time Limit Exceeded

Solution code:
from queue import PriorityQueue as PQ

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = PQ()
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put([dist[v], v])
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = {}
adjt = {}
for i in range(n+1):
	adjs[i] = []
	adjt[i] = []
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

tab = [0]*(n+1)
for i in range(1,n+1):
	tab[i] = dist_s[i] + dist_t[i]
	# ~ print("echange",i," = ",tab[i])
	# ~ tab[i] = yen - tab[i]

ans = [0]*(n+1)
ans[n] = tab[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], tab[i])
	
for i in range(n):
	print(yen - ans[i+1])