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: Wrong Answer

Solution code:
import heapq
n, m, s, t = [int(i) for i in input().split()]
s -= 1
t -= 1
snuuk_dict = dict()
yen_dict = dict()
snuuk_que = []
yen_que = []
for i in range(m):
    u, v, a, b = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    if snuuk_dict.get(u) is None:
        snuuk_dict[u] = []
        yen_dict[u] = []
    if snuuk_dict.get(v) is None:
        snuuk_dict[v] = []
        yen_dict[v] = []
    snuuk_dict[u].append([b, u, v])
    snuuk_dict[v].append([b, v, u])
    yen_dict[u].append([a, u, v])
    yen_dict[v].append([a, v, u])

for i in snuuk_dict[t]:
    heapq.heappush(snuuk_que, i)
for i in yen_dict[s]:
    heapq.heappush(yen_que, i)
snuuk_ls = [-1 for i in range(n)]
yen_ls = [-1 for i in range(n)]
yen_ls[s] = 0
snuuk_ls[t] = 0
while len(yen_que) > 0:
    a, u, v = heapq.heappop(yen_que)
    if yen_ls[v] != -1:
        continue
    yen_ls[v] = a
    for i in yen_dict[v]:
        heapq.heappush(yen_que, [i[0] + yen_ls[v], i[1], i[2]])
while len(snuuk_que) > 0:
    b, v, u = heapq.heappop(snuuk_que)
    if snuuk_ls[u] != -1:
        continue
    snuuk_ls[u] = b
    for i in snuuk_dict[u]:
        heapq.heappush(snuuk_que,  [i[0] + snuuk_ls[u], i[1], i[2]])
for i in range(n):
    print(10**15 - (yen_ls[i] + snuuk_ls[i]))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, i):
    INF = float('inf')

    H = []
    d = 0
    D = [INF] * V
    D[i] = 0
    used = [False] * V
    used[i] = True

    while True:
        for j in G[i].keys():
            heapq.heappush(H, (d + G[i][j], j))
        v = -1
        while H:
            d, j = heapq.heappop(H)
            if not used[j]:
                v = j
                break
        if v == -1:
            break
        else:
            used[v] = True
            D[v] = d
            i = v
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(dict)
graph_s = defaultdict(dict)

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

print(graph_y)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(list)
graph_s = defaultdict(list)

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(list)
graph_s = defaultdict(list)

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


dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for u, w in graph_y[v]:
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(list)
graph_s = defaultdict(list)

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(list)
graph_s = defaultdict(list)

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


dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for u, w in graph_y[v]:
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))


dist_node_st = defaultdict(lambda: float("inf"))
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for u, w in graph_s[v]:
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(list)
graph_s = defaultdict(list)

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

dist_node_ys = [float("inf") for i in range(n)]
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v= heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for u, w in graph_y[v]:
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))

dist_node_st = [float("inf") for i in range(n)]
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for u, w in graph_s[v]:
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

print(dist_node_st)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
n,m,s,t=map(int,input().split())
ans=10**15
h=10**15
snuuk=[[float('inf') for i in range(n)]for j in range(n)]
yen=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    snuuk[u-1][v-1]=b
    snuuk[v-1][u-1]=b
    yen[u-1][v-1]=a
    yen[v-1][u-1]=a
cost_snuuk=dijkstra(snuuk,directed=False,unweighted=False)
cost_yen=dijkstra(yen,directed=False,unweighted=False)
for j in range(m+1):
    ans=10**15
    for i in range(n):
        if j<=i:
            ans=min(ans,cost_yen[s-1][i]+cost_snuuk[i][t-1])
    print(int(h-ans))

Submission status: Wrong Answer

Solution code:
import heapq

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

def dijkstra(graph, start):
    dist = [ 10**14 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [ dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)
ans = 10**14
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuuk[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Wrong Answer

Solution code:
import heapq

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

def dijkstra(graph, start):
    dist = [ 10**15 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)
ans = 10**14
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuuk[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

def dijkstra(G,D,x,n):
    #Gは隣接頂点
    #Dは各頂点間の距離、逆向きも加えておく(有向なら片方だけ)
    #xはスタート地点
    #nは頂点数
    V = [ 0 for _ in range(n)] #Vはその頂点が確定しているかどうか、確定なら1
    X = [ 10**14 for _ in range(n)] #不確定な経路
    W = [ 0 for _ in range(n)] #Wは最短経路
    H = [(0,x)]
    heapq.heapify(H)
    while H:
        d, p = heapq.heappop(H)
        W[p] = d
        V[p] = 1
        for y in G[p]:
            if V[y] == 0:
                X[y] = min( X[y], d+D[(y,p)])
                heapq.heappush(H, (min(X[y], d + D[(y,p)]),y))
    return W                

n, m, s, t = map( int, input().split())
s, t = s-1, t-1
D_yen = dict()
D_snuke = dict()
G = [ [] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    G[u].append(v)
    G[v].append(u)
    D_yen[(u,v)] = D_yen[(v,u)] = a
    D_snuke[(u,v)] = D_snuke[(v,u)] = b
C_yen = dijkstra(G,D_yen,s,n)
C_snuke = dijkstra(G,D_snuke,t,n)
ans = 10**14
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuke[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

def dijkstra(G,D,x,n):
    #Gは隣接頂点
    #Dは各頂点間の距離、逆向きも加えておく(有向なら片方だけ)
    #xはスタート地点
    #nは頂点数
    V = [ 0 for _ in range(n)] #Vはその頂点が確定しているかどうか、確定なら1
    X = [ 10**14 for _ in range(n)] #不確定な経路
    W = [ 0 for _ in range(n)] #Wは最短経路
    H = [(x,0)]
    heapq.heapify(H)
    while H:
        p, d = heapq.heappop(H)
        W[p] = d
        V[p] = 1
        for y in G[p]:
            if V[y] == 0:
                X[y] = min( X[y], d+D[(y,p)])
                heapq.heappush(H, (y,min(X[y], d + D[(y,p)])))
    return W                

n, m, s, t = map( int, input().split())
s, t = s-1, t-1
D_yen = dict()
D_snuke = dict()
G = [ [] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    G[u].append(v)
    G[v].append(u)
    D_yen[(u,v)] = D_yen[(v,u)] = a
    D_snuke[(u,v)] = D_snuke[(v,u)] = b
C_yen = dijkstra(G,D_yen,s,n)
C_snuke = dijkstra(G,D_snuke,t,n)
ans = 10**14
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuke[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Wrong Answer

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



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


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n:
			quit()

Submission status: Wrong Answer

Solution code:
from heapq import *
from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * n
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[p[0]]:
            continue
        visited[p[0]] = True
        for i in range(len(G[v])):
            if visited[p[0]]:
                continue
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


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

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Wrong Answer

Solution code:
from heapq import *
from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[]]*n
Gb = [[]]*n
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Wrong Answer

Solution code:
from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from numpy import array,inf


def djikstra(s):
    que = PriorityQueue()
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                que.push((d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[]]*n
Gb = [[]]*n
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Wrong Answer

Solution code:
from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from numpy import array,inf


def djikstra(s):
    que = PriorityQueue()
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                que.push((d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[]]*n
Gb = [[]]*n
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = array(S)+array(T)

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

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np

class vertex:
    def __init__(self):
        self.list_adj = []  # list of [no_adjnode, a, b]

    def add_edge(self, adj):
        self.list_adj.append(adj)

n, m, s, t = map(int, input().split())
# zero start
s -= 1
t -= 1

# 
vertices = []
for i in range(n):
    v = vertex()
    vertices.append(v)

#print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].add_edge([v-1, a, b])
    vertices[v-1].add_edge([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)
#for i in range(n):
#    print(vertices[i].list_adj)

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in v.list_adj:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = int(10e20)
    dist = [inf] * n
    h = []
    heappush(h, (0, s))
    while len(h) > 0:
        # pop 1 node
        dv, v = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(vertices[v])
        for adj in list_adj:
            if dist[adj[0]] == inf:
                heappush(h, (dv + adj[1], adj[0]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
#cost = []
#for k in range(len(dist_a)):
#    cost.append(dist_a[k] + dist_b[k])
cost = np.array(dist_a,dtype = 'int') + np.array(dist_b,dtype = 'int')
cost = np.array(cost, dtype='int')
#print(cost)

m0 = int(10e15)
for i in range(n):
    cost_available = cost[i:]
    print(m0-np.amin(cost_available))

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np

class vertex:
    def __init__(self):
        self.list_adj = []  # list of [no_adjnode, a, b]

    def add_edge(self, adj):
        self.list_adj.append(adj)

n, m, s, t = map(int, input().split())
# zero start
s -= 1
t -= 1

# 
vertices = []
for i in range(n):
    v = vertex()
    vertices.append(v)

print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].add_edge([v-1, a, b])
    vertices[v-1].add_edge([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)
#for i in range(n):
#    print(vertices[i].list_adj)

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in v.list_adj:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = int(10e20)
    dist = [inf] * n
    h = []
    heappush(h, (0, s))
    while len(h) > 0:
        # pop 1 node
        dv, v = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(vertices[v])
        for adj in list_adj:
            if dist[adj[0]] == inf:
                heappush(h, (dv + adj[1], adj[0]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
#cost = []
#for k in range(len(dist_a)):
#    cost.append(dist_a[k] + dist_b[k])
cost = np.array(dist_a,dtype = 'int') + np.array(dist_b,dtype = 'int')
cost = np.array(cost, dtype='int')
#print(cost)

m0 = int(10e15)
for i in range(n):
    cost_available = cost[i:]
    print(m0-np.amin(cost_available))

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np

class vertex:
    def __init__(self):
        self.list_adj = []  # list of [no_adjnode, a, b]

    def add_edge(self, adj):
        self.list_adj.append(adj)

n, m, s, t = map(int, input().split())
# zero start
s -= 1
t -= 1

# 
vertices = []
for i in range(n):
    v = vertex()
    vertices.append(v)

print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].add_edge([v-1, a, b])
    vertices[v-1].add_edge([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)
#for i in range(n):
#    print(vertices[i].list_adj)

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in v.list_adj:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = int(10e20)
    dist = [inf] * n
    h = []
    heappush(h, (s, 0))
    while len(h) > 0:
        # pop 1 node
        v, dv = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(vertices[v])
        for adj in list_adj:
            if dist[adj[0]] == inf:
                heappush(h, (adj[0], dv + adj[1]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
#cost = []
#for k in range(len(dist_a)):
#    cost.append(dist_a[k] + dist_b[k])
cost = np.array(dist_a,dtype = 'int') + np.array(dist_b,dtype = 'int')
cost = np.array(cost, dtype='int')
#print(cost)

m0 = int(10e15)
for i in range(n):
    cost_available = cost[i:]
    print(m0-np.amin(cost_available))

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np

class vertex:
    def __init__(self):
        self.list_adj = []  # list of [no_adjnode, a, b]

    def add_edge(self, adj):
        self.list_adj.append(adj)

n, m, s, t = map(int, input().split())
# zero start
s -= 1
t -= 1

# 
vertices = []
for i in range(n):
    v = vertex()
    vertices.append(v)

print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].add_edge([v-1, a, b])
    vertices[v-1].add_edge([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)
#for i in range(n):
#    print(vertices[i].list_adj)

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in v.list_adj:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = 10e20
    dist = [inf] * n
    h = []
    heappush(h, (s, 0))
    while len(h) > 0:
        # pop 1 node
        v, dv = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(vertices[v])
        for adj in list_adj:
            if dist[adj[0]] == inf:
                heappush(h, (adj[0], dv + adj[1]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
cost = np.array(dist_a) + np.array(dist_b)
cost = np.array(cost, dtype='int')
#print(cost)

m0 = int(10e15)
for i in range(n):
    cost_available = cost[i:]
    print(m0-np.amin(cost_available))

Submission status: Wrong Answer

Solution code:

import heapq as hq

INF = 10**16
OKANE = 10**15



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

graph_yen = [[] for _ in range(N+1)]
graph_snk = [[] for _ in range(N+1)]


for i in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen[u].append((a, v))
    graph_yen[v].append((a, u))
    graph_snk[u].append((b, v))
    graph_snk[v].append((b, u))


def dijkstra(st, graph, N):
    dist = [INF]*(N+1)
    hasVisited = [False]*(N+1)
    hasVisited[0] = True
    
    dist[st] = 0
    hasVisited[st] = True
    
    # startをpushする
    cand_list = []
    hq.heappush(cand_list, (0,st))
    while len(cand_list) != 0:
        nex, node = hq.heappop(cand_list)
        if dist[node] < nex:
            continue

        for nb in graph[node]:
            if dist[nb[1]] > nex+nb[0]:
                dist[nb[1]] = nex+nb[0]
                hq.heappush(cand_list,(dist[nb[1]], nb[1]))
    
    return dist


dist_yen = dijkstra(S,graph_yen, N)
dist_snk = dijkstra(T,graph_snk, N)

del dist_yen[0]
del dist_snk[0]


min_list = [INF]
i = 0
for yen, snk in zip(dist_yen[::-1], dist_snk[::-1]):
    min_after_i = yen+snk
    min_list.append(min(min_after_i,min_list[i-1]))
    i+=1

del min_list[0]

for cost in min_list[::-1]:
    print(OKANE - cost)

Submission status: Wrong Answer

Solution code:

import heapq as hq

INF = 10**16
OKANE = 10**15

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

graph_yen = [[] for _ in range(N+1)]
graph_snk = [[] for _ in range(N+1)]


for i in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snk[u].append((v, b))
    graph_snk[v].append((u, b))


def dijkstra(st, graph, N):
    dist = [INF]*(N+1)
    hasVisited = [False]*(N+1)
    hasVisited[0] = True
    
    dist[st] = 0
    hasVisited[st] = True
    
    # ryogaeをvisitするまで続く
    cand_list = []
    cr_point = st
    while (False in hasVisited):
        # 次の候補をheapに入れる
        for neighb in graph[cr_point]:
            if not hasVisited[neighb[0]]:
                cand_list.append([dist[cr_point]+neighb[1], neighb[0]])
            
        #print("cand_list:{}".format(cand_list))
        # 次の候補を確定
        hq.heapify(cand_list)
        while 1:
            next_node = hq.heappop(cand_list)
            if not hasVisited[next_node[1]]:
                break
         
        #print(next_node)
        # distの更新
        cr_point = next_node[1]
        dist[cr_point] = next_node[0]
        hasVisited[cr_point] = True
        
        #print("dist:{}".format(dist))
    
    return dist


dist_yen = dijkstra(S,graph_yen, N)
dist_snk = dijkstra(T,graph_snk, N)
del dist_yen[0]
del dist_snk[0]

min_list = [INF]
i = 0
for yen, snk in zip(dist_yen[::-1], dist_snk[::-1]):
    min_after_i = yen+snk
    min_list.append(min(min_after_i,min_list[i-1]))
    i+=1

del min_list[0]

for cost in min_list[::-1]:
    print(OKANE - cost)

Submission status: Wrong Answer

Solution code:
import heapq as hq
from collections import deque
n,m,s,t=map(int,input().split())
#リンク情報をつくる
yenLinks={}
snkLinks={}
for _ in range(m):
    u,v,a,b=map(int,input().split())
    if u not in yenLinks:
        yenLinks[u]=[(v,a)]
        snkLinks[u]=[(v,b)]
    else:
        yenLinks[u].append((v,a))
        snkLinks[u].append((v,b))
    if v not in yenLinks:
        yenLinks[v]=[(u,a)]
        snkLinks[v]=[(u,b)]
    else:
        yenLinks[v].append((u,a))
        snkLinks[v].append((u,b))
#Dijkstra法をする関数
INF=10**9+7
def dijkstra(start,links,nodeNum):
    ans=[INF for _ in range(nodeNum+1)]
    ans[start]=0
    PQ=[(0,start)]
    hq.heapify(PQ)
    while PQ:
        (Vd,V) = hq.heappop(PQ)
        #print([V,Vd,ans[V]])
        if Vd > ans[V]:
            continue
        for (W,D) in links[V]:
            cand = ans[V] + D
            if cand < ans[W]:
                ans[W] = cand
                hq.heappush(PQ,(ans[W],W))
            #print(PQ)
    return(ans)
#Dijkstra法実行
yenKstra=dijkstra(s,yenLinks,n)
snkKstra=dijkstra(t,snkLinks,n)
#答えを求める
i=n
ans=INF
answers=[]
while i>0:
    cand = yenKstra[i]+snkKstra[i]
    ans = min(ans,cand)
    answers.append(10**15-ans)
    i-=1
answers.reverse()
#出力
for ans in answers:
    print(ans)