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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N,M,S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,a,b = map(int,input().split())
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1]

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N,M,S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,a,b = map(int,input().split())
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1]

print(*answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

N,M,S,T = map(int,input().split())
UVAB = [[int(x) for x in input().split()] for _ in range(M)]
U,V,A,B = zip(*UVAB)

g1 = csr_matrix((A,(U,V)), (N+1,N+1))
g2 = csr_matrix((B,(U,V)), (N+1,N+1))
d1 = dijkstra(g1, indices=S, directed=False)
d2 = dijkstra(g2, indices=T, directed=False)

d = d1 + d2 # 各頂点を両替所に選ぶ場合

d = (np.minimum.accumulate(d[::-1])[::-1]).astype(int)

answer = 10 ** 10 - d[1:]
print(*answer, sep='\n')

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input=sys.stdin.readline
N,m,s,t=map(int,input().split())
E=[[]for i in range(N+1)]
S=[[]for i in range(N+1)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    E[u].append([v,a])
    E[v].append([u,a])
    S[u].append([v,b])
    S[v].append([u,b])
    
Q=[]
C=[1 for i in range(N+1)]
for i in E[s]:
    Q.append([i[1],i[0]])
    C[i[0]]=0
heapq.heapify(Q)

A=[10**15 for i in range(N+1)]
A[s]=0
C[s]=0
for i in range(10**6):
    #print(len(Q))
    if len(Q)==0:
        break
    else:
        q=Q[0]
        A[q[1]]=q[0]
        for j in E[q[1]]:
            if C[j[0]]!=0:
                heapq.heappush(Q,[j[1]+q[0],j[0]])
                C[j[0]]=0
        heapq.heappop(Q)
#print(E)
#print(A)
#print(C)
Q=[]
C=[1 for i in range(N+1)]
for i in S[t]:
    Q.append([i[1],i[0]])
    C[i[0]]=0
heapq.heapify(Q)

B=[10**15 for i in range(N+1)]
B[t]=0
C[t]=0
for i in range(10**6):
    #print(len(Q))
    if len(Q)==0:
        break
    else:
        q=Q[0]
        B[q[1]]=q[0]
        for j in S[q[1]]:
            if C[j[0]]!=0:
                heapq.heappush(Q,[j[1]+q[0],j[0]])
                C[j[0]]=0
        heapq.heappop(Q)
#print(B)
ans=[]
heapq.heapify(ans)
for i in range(1,N+1):
    heapq.heappush(ans,[A[i]+B[i],i])
    
for i in range(N):
    if len(ans)==0:
        break
    while ans[0][1]<=i:
        heapq.heappop(ans)
    print(10**15-ans[0][0])

Submission status: Wrong Answer

Solution code:

from collections import defaultdict

def get_dikstra(graph_data, weigh_data, node_num, edge_num, start):
    dist_data = [-1 for i in range(node_num + 1)]
    dist_data[start] = 0
    check_num = set()
    check_num.add(start)

    for i in range(node_num - 1):
        next_dist = 10 ** 10
        next_ind = -1

        for now_ele in check_num:
            for next_ele in graph_data[now_ele]:
                if dist_data[next_ele] != -1:
                    continue
                kari_dist = dist_data[now_ele] + weigh_data[(now_ele, next_ele)]
                if kari_dist < next_dist:
                    next_dist = kari_dist
                    next_ind = next_ele
        dist_data[next_ind] = next_dist
        check_num.add(next_ind)

    return dist_data


def main():
    node_num, edge_num, start, goal = map(int, input().split())
    graph_data = defaultdict(set)
    yen_data = defaultdict(int)
    knoke_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c, d = map(int, input().split())
        graph_data[a].add(b)
        graph_data[b].add(a)
        yen_data[(a, b)] = c
        yen_data[(b, a)] = c
        knoke_data[(a, b)] = d
        knoke_data[(b, a)] = d

    yen_dist = get_dikstra(graph_data, yen_data, node_num, edge_num, start)
    knoke_dist = get_dikstra(graph_data, knoke_data, node_num, edge_num, goal)

    ans_list = [0 for i in range(node_num + 1)]

    ans_list[node_num] = yen_dist[node_num] + knoke_dist[node_num]
    for i in range(1, node_num)[::-1]:
        ans_list[i] = min(ans_list[i + 1], yen_dist[i] + knoke_dist[i])

    first = 10 ** 15
    for i in range(1, node_num + 1):
        print(first - ans_list[i])





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

n,m,s,t=map(int,input().split())
E=[[] for i in range(n+1)]
S=[[] for i in range(n+1)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    E[u].append([a,v,u])
    E[v].append([a,u,v])
    S[u].append([b,v,u])
    S[v].append([b,u,v])
#print(E)

VE=[1 for i in range(n+1)]
DE=[-1 for i in range(n+1)]
EQ=E[s]
heapq.heapify(EQ)
DE[s]=0
VE[s]=0
#print(EQ[0])
for i in range(10**7):
    if len(EQ)==0:
        break
    else:
        if VE[EQ[0][1]]==1:
            VE[EQ[0][1]]=0
            DE[EQ[0][1]]=DE[EQ[0][2]]+EQ[0][0]
            A=EQ[0][1]
            heapq.heappop(EQ)
            for j in E[A]:
                heapq.heappush(EQ,j)
        else:
            heapq.heappop(EQ)
#print(DE)
VS=[1 for i in range(n+1)]
DS=[-1 for i in range(n+1)]
SQ=S[t]
heapq.heapify(SQ)
DS[t]=0
VS[t]=0
#print(SQ[0])
for i in range(10**7):
    if len(SQ)==0:
        break
    else:
        if VS[SQ[0][1]]==1:
            VS[SQ[0][1]]=0
            DS[SQ[0][1]]=DS[SQ[0][2]]+SQ[0][0]
            A=SQ[0][1]
            heapq.heappop(SQ)
            for j in S[A]:
                heapq.heappush(SQ,j)
        else:
            heapq.heappop(SQ)
#print(DS)
            
ANS=[]
for i in range(1,n+1):
    ANS.append([DE[i]+DS[i],i])
#print(ANS)
heapq.heapify(ANS)
for i in range(n):
    if i<ANS[0][1]:
        print(10**15-ANS[0][0])
    else:
        for j in range(n+1):
            if i>=ANS[0][1]:
                heapq.heappop(ANS)
            else:
                print(10**15-ANS[0][0])
                break

Submission status: Wrong Answer

Solution code:
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**13
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N, M, S, T = map(int, input().split())
VA = [[] for i in range(N)]
VB = [[] for i in range(N)]
for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    VA[u-1].append([v-1, a])
    VA[v-1].append([u-1, a])
    VB[u-1].append([v-1, b])
    VB[v-1].append([u-1, b])

da = dijkstra(S-1, VA)
db = dijkstra(T-1, VB)
tmp = 10**16
base = 10 ** 15
ans = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = min(da[i] + db[i], tmp)
    ans[i] = tmp

for i in range(N):
    print(base - ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


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

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

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

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

      
N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

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

result_a = graph1.search(S)
result_b = graph2.search(T)
ans_list = [float('inf')]
for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


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

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

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

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

      
N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

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

result_a = graph1.search(S)
result_b = graph2.search(T)
ans_list = [float('inf')]
for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

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

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**9

n, m, s, t = [int(item) for item in input().split()]
yen = [[] for _ in range(n)]
snk = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist

for i in range(m):
    u, v, a, b = [int(item) for item in input().split()]
    u-=1; v-=1
    yen[u].append([v, a])
    yen[v].append([u, a])
    snk[u].append([v, b])
    snk[v].append([u, b])

yen_dijk = Dijkstra(yen)
snk_dijk = Dijkstra(snk)

yen_dist = yen_dijk.calc(s-1)
snk_dist = snk_dijk.calc(t-1)
 
ans = [0] * n
min_cost = 10**15
i = n-1
for yy, ss in zip(yen_dist[::-1], snk_dist[::-1]):
    min_cost = min(min_cost, yy + ss)
    ans[i] = min_cost
    i -= 1

for item in ans:
    print(10**15 - item)

Submission status: Wrong Answer

Solution code:
class Dijkstra():
    def __init__(self, N):
        self.N = N
        self.e = [[float('inf') for i in range(self.N)] for i in range(N)]

    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u][v] = d
            self.e[v][u] = d
        else:
            self.e[u][v] = d

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def DijkstraSearch(self, s):
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        pred = [-1 for i in range(self.N)]
        visited = [False for i in range(self.N)]

        while True:
            u = -1
            sd = float('inf')
            for i in range(0, self.N):
                if not visited[i] and d[i] < sd:
                    sd = d[s]
                    u = i

            if u == -1:
                break

            visited[u] = True
            for v in range(0, self.N):
                w = self.e[u][v]
                if v == u:
                    continue
                newLen = d[u] + w
                if newLen < d[v]:
                    d[v] = newLen
                    pred[v] = u
        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra(N)
graph2 = Dijkstra(N)

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

result_a = graph1.DijkstraSearch(S-1)
result_b = graph2.DijkstraSearch(T-1)
ans_list = [float('inf')]
for i in range(N-1, -1, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        check[src]=True
        for dst, d1 in paths[src]:
            if check[dst] is False and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(10**15-mindst)

for dst in ans[::-1]:
    print(dst)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        check[src]=True
        for dst, d1 in paths[src]:
            if check[dst] is False and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(10**15-mindst)

for dst in ans[::-1]:
    print(dst)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        check[src]=True
        for dst, d1 in paths[src]:
            if check[dst] is False and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(10**15-mindst)

for dst in ans[::-1]:
    print(-dst)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        check[src]=True
        for dst, d1 in paths[src]:
            if check[dst] is False and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)
print(paths_yn)
print(shortest_yn)
print(paths_sn)
print(shortest_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(mindst)

for dst in ans[::-1]:
    print(10**15-dst)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while q:
        d0, src=heappop(q)
        check[src]=True
        for dst, d1 in paths[src]:
            if (not check[dst]) and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(mindst)

for dst in ans[::-1]:
    print(10**15-dst)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF=10**10
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=defaultdict(lambda: INF)
    shortest[S]=0
    while q:
        d0, src=heappop(q)
        check[src]=True
        for dst, d1 in paths[src]:
            if not check[dst] and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return shortest

paths_yn=defaultdict(list)
paths_sn=defaultdict(list)
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

ans=[]
mindst=10**10
for i in list(range(N))[::-1]:
    tmp = shortest_yn[i] + shortest_sn[i]
    mindst = min(mindst, tmp)
    ans.append(mindst)

for dst in ans[::-1]:
    print(10**15-dst)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph) + 1)]
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        dist[v] = w
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist[:-1]


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import defaultdict
N,M,S,T=[int(a) for a in input().split(" ")]
S,T=S-1,T-1
UVAB = [[int(a) for a in input().split(" ")] for i in range(M)]
dic = defaultdict(list)
INF = 10**20
check = [False]*(2*N)

for u, v, a, b in UVAB:
    dic[u-1].append((v-1,a))
    dic[v-1].append((u-1,a))
    dic[u+N-1].append((v+N-1,b))
    dic[v+N-1].append((u+N-1,b))

ans = []
for i in list(range(N))[::-1]:
    dic[i].append((i+N,0))
    dic_dist = defaultdict(lambda: INF)
    dic_dist[S] = 0
    q = [(0, S)]
    while(q):
        d0, node = heappop(q)
        check[node] = True
        if dic_dist[node] < d0:
            continue
        for dst, d1 in dic[node]:
            if not check[dst] and dic_dist[dst] > d0+d1:
                dic_dist[dst] = d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    ans.append(10**15-dic_dist[T+N])

for line in ans[::-1]:
    print(line)

Submission status: Wrong Answer

Solution code:
import heapq
from itertools import accumulate

def dijkstra(ad_lst, n, s, t):
    inf = float('inf')
    costs = [inf for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

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

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
result=list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1],min))
yen = 10**15
[print(yen-result[i]) for i in range(n, -1)]

Submission status: Wrong Answer

Solution code:
import heapq
from itertools import accumulate

def dijkstra(ad_lst, n, s, t):
    inf = float('inf')
    costs = [inf for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

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

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
result=list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1],min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1)]

Submission status: Wrong Answer

Solution code:
import heapq
from itertools import accumulate

def dijkstra(ad_lst, n, s, t):
    inf = float('inf')
    costs = [inf for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

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

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
result=list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1],min))
yen = 10**15
print(result)
[print(yen-result[i]) for i in range(n-1, -1, -1)]

Submission status: Wrong Answer

Solution code:
import heapq
from itertools import accumulate

def dijkstra(ad_lst, n, s, t):
    inf = float('inf')
    costs = [inf for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

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

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
result=list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1],min))
yen = 10**15
[print(yen-result[i]) for i in range(n+1, 0)]

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
n,m,s,t = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = (int(i) for i in input().split())
    x[u].append((v,a))
    x[v].append((u,a))
    y[u].append((v,b))
    y[v].append((u,b))
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
X,Y,z = dijkstra(n,s,x),dijkstra(n,t,y),[]
for i in range(1,n+1): z.append((X[i]+Y[i],i))
z,k = sorted(z),0
for i in range(n):
    while z[k][1]<=i: k+=1
    print(z[k][0])