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:
from collections import defaultdict

money = 10 ** 15
inf = float('inf')

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

edges = defaultdict(dict)
for i in range(1, M + 1):
    u, v, a, b = map(int, input().split())
    edges[u][v] = {"a": a, "b": b}
    edges[v][u] = {"a": a, "b": b}

costs_y = defaultdict(int)
costs_s = defaultdict(int)

def find_lowest_cost_node(costs, processed):
    lowest_cost = inf
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Sから両替所候補となる各ノードへの円を使った最短距離を計算する
temp_processed = []
for i in range(1, N + 1):
    if i is S:
        costs_y[i] = 0
    else:
        costs_y[i] = inf

node = find_lowest_cost_node(costs_y, temp_processed)
while node is not None:
    cost = costs_y[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["a"]
        if costs_y[n] > new_cost:
            costs_y[n] = new_cost
    temp_processed.append(node)
    node = find_lowest_cost_node(costs_y, temp_processed)

# 両替所候補となる各ノードからTへのスヌークを使った最短距離を計算する
temp_processed = []
for i in range(1, N + 1):
    if i is T:
        costs_s[i] = 0
    else:
        costs_s[i] = inf

node = find_lowest_cost_node(costs_s, temp_processed)
while node is not None:
    cost = costs_s[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["b"]
        if costs_s[n] > new_cost:
            costs_s[n] = new_cost
    temp_processed.append(node)
    node = find_lowest_cost_node(costs_s, temp_processed)


# S->i + i->T の合計コスト
total_costs = []
for i in range(1, N + 1):
    total_costs.append(costs_y[i] + costs_s[i])

for i in range(N):
    print(money - min(total_costs[i:]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

money = 10 ** 15
N, M, S, T = map(int, input().split())

edges = defaultdict(dict)
for i in range(1, M + 1):
    u, v, a, b = map(int, input().split())
    edges[u][v] = {"a": a, "b": b}
    edges[v][u] = {"a": a, "b": b}

inf = float('inf')
costs_from_S_by_y = defaultdict(int)
costs_to_T_by_s = defaultdict(int)

def find_lowest_cost_node(costs, processed):
    lowest_cost = inf
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Sから両替所候補となる各ノードへの円を使った最短距離を計算する
temp_processed = []
temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is S:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["a"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_from_S_by_y[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)

# 両替所候補となる各ノードからTへのスヌークを使った最短距離を計算する
temp_processed = []
temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is T:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["b"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_to_T_by_s[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)


# S->i + i->T の合計コスト
total_costs = []
for i in range(1, N + 1):
    total_costs.append(costs_from_S_by_y[i] + costs_to_T_by_s[i])

for i in range(N):
    print(money - min(total_costs[i:]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

edges = defaultdict(dict)
for i in range(1, M + 1):
    u, v, a, b = map(int, input().split())
    edges[u][v] = {"a": a, "b": b}
    edges[v][u] = {"a": a, "b": b}

inf = float('inf')
costs_from_S_by_y = defaultdict(int)
costs_to_T_by_s = defaultdict(int)

def find_lowest_cost_node(costs, processed):
    lowest_cost = inf
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Sから両替所候補となる各ノードへの円を使った最短距離を計算する
temp_processed = []

temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is S:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["a"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_from_S_by_y[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)

# 両替所候補となる各ノードからTへのスヌークを使った最短距離を計算する
temp_processed = []

temp_costs = defaultdict(int)
for i in range(1, N + 1):
    if i is T:
        temp_costs[i] = 0
    else:
        temp_costs[i] = inf

node = find_lowest_cost_node(temp_costs, temp_processed)
while node is not None:
    cost = temp_costs[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["b"]
        if temp_costs[n] > new_cost:
            temp_costs[n] = new_cost
    costs_to_T_by_s[node] = temp_costs[node]
    temp_processed.append(node)
    node = find_lowest_cost_node(temp_costs, temp_processed)


# S->i + i->T の合計コスト
total_costs = []
for i in range(1, N + 1):
    total_costs.append(costs_from_S_by_y[i] + costs_to_T_by_s[i])

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        for nv, nd in edge[v]:
            if dist[nv] == float("inf"):
                dist[nv] = dist[v] + nd
                heapq.heappush(que, (dist[nv], nv))
            elif dist[nv] > dist[v] + nd:
                dist[nv] = dist[v] + nd
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import heapq

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        for nv, nd in edge[v]:
            if dist[nv] == float("inf"):
                dist[nv] = dist[v] + nd
                heapq.heappush(que, (dist[nv], nv))
            elif dist[nv] > dist[v] + nd:
                dist[nv] = dist[v] + nd
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
INF=10000000000
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        minc,u=heappop(que)
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[u]+c,v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[(enc[i]+snc[i],i) for i in range(n)]
heapify(res)
for i in range(n):
    while(res[0][1]<i):
        heappop(res)
    print(10**15-res[0][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
INF=10000000000
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        minc,u=heappop(que)
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[u]+c,v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[[enc[i]+snc[i],i] for i in range(n)]
res=sorted(res,key=lambda res:res[0])
p=0
for i in range(n):
    while(res[p][1]<i):
        p+=1
    print(int(1e+15)-res[p][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
INF=10000000000
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        minc,u=heappop(que)
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[u]+c,v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[[0,i] for i in range(n)]
for i in range(n):
    res[i][0]=enc[i]+snc[i]
res=sorted(res,key=lambda res:res[0])
p=0
for i in range(n):
    if(res[p][1]<i):
        p+=1
    print(int(1e+15)-res[p][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
INF=10000000000
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        minc,u=heappop(que)
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[u]+c,v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[[0,i] for i in range(n)]
for i in range(n):
    res[i][0]=enc[i]+snc[i]
res=sorted(res,key=lambda res:res[0])
p=0
for i in range(n):
    if(res[p][1]<i):
        p+=1
    print(int(10e+15)-res[p][0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] # 円のグラフ
c = [[] for i in range(n)] # スヌークのグラフ

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    INF=pow(10,20)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=pow(10,10)
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

for i in range(n):
    print(pow(10,15)-ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] # 円のグラフ
c = [[] for i in range(n)] # スヌークのグラフ

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    INF=pow(10,15)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=pow(10,10)
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

for i in range(n):
    print(pow(10,15)-ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] # 円のグラフ
c = [[] for i in range(n)] # スヌークのグラフ

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    INF=pow(10,10)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=pow(10,10)
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

for i in range(n):
    print(pow(10,15)-ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import fractions
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def verify(graph, start, n):
    h = []
    for edge in graph[start]:
        heapq.heappush(h, edge)
    cost = [INF for i in range(n)]
    cost[start] = 0
    while(h):
        tcost, cur, tgt = heapq.heappop(h)
        if cost[cur] + tcost < cost[tgt]:
            cost[tgt] = cost[cur] + tcost
            for edge in graph[tgt]:
                heapq.heappush(h, edge)

    return cost

def main():
    money = 10 ** 15
    n,m,s,t = getlist()
    yengraph = [[] for i in range(n)]
    snuukgraph = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = getlist()
        yengraph[a - 1].append((c, a- 1, b - 1))
        yengraph[b - 1].append((c, b-1, a - 1))
        snuukgraph[a - 1].append((d, a-1, b - 1))
        snuukgraph[b - 1].append((d, b-1, a - 1))

    ycost = verify(yengraph, s-1, n)
    scost = verify(snuukgraph, t-1, n)

    sumcost = []
    idx = 1
    for y, s in zip(ycost, scost):
        sumcost.append((y+s, idx))
        idx += 1
    sumcost.sort()
    idx = 0
    print(1)
    # for i in range(n):
    #     while(True):
    #         ans, cid = sumcost[idx]
    #         if cid > i:
    #             print(money - ans)
    #             break
    #         else:
    #             idx += 1
    # # print(ycost)
    # print(scost)
    # print(sumcost)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import fractions
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def verify(graph, start, n):
    h = []
    for edge in graph[start]:
        heapq.heappush(h, edge)
    cost = [INF for i in range(n)]
    cost[start] = 0
    while(h):
        tcost, cur, tgt = heapq.heappop(h)
        if cost[cur] + tcost < cost[tgt]:
            cost[tgt] = cost[cur] + tcost
            for edge in graph[tgt]:
                heapq.heappush(h, edge)

    return cost

def main():
    money = 10 ** 15
    n,m,s,t = getlist()
    yengraph = [[] for i in range(n)]
    snuukgraph = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = getlist()
        yengraph[a - 1].append((c, a- 1, b - 1))
        yengraph[b - 1].append((c, b-1, a - 1))
        snuukgraph[a - 1].append((d, a-1, b - 1))
        snuukgraph[b - 1].append((d, b-1, a - 1))

    ycost = verify(yengraph, s-1, n)
    scost = verify(snuukgraph, t-1, n)

    sumcost = []
    idx = 1
    for y, s in zip(ycost, scost):
        sumcost.append((y+s, idx))
        idx += 1
    sumcost.sort()
    idx = 0
    for i in range(n):
        print(1)
    #     while(True):
    #         ans, cid = sumcost[idx]
    #         if cid > i:
    #             print(money - ans)
    #             break
    #         else:
    #             idx += 1
    # # print(ycost)
    # print(scost)
    # print(sumcost)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 9999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
n,m,s,t = inm()
dst = [{} for i in range(n)]
for i in range(m):
    u,v,a,b = inm()
    dst[u-1][v-1] = (a,b)
    dst[v-1][u-1] = (a,b)

costa = [BIG]*n
costb = [BIG]*n
q = [(0,s-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costa[p]<=d:
        continue
    costa[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][0], v))

q = [(0,t-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costb[p]<=d:
        continue
    costb[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][1], v))

#ddprint(costa)
#ddprint(costb)

mn = BIG
ans = []
for i in range(n-1,-1,-1):
    mn = min(mn, costa[i]+costb[i])
    ans.append(mn)
for i in range(n-1,-1,-1):
    print(10**15-ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, s, t = map(int, input().split())
e = dd(list)
ee = dd(list)
for i in range(M):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  ee[u].append((v, b))
  ee[v].append((u, b))

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 10)
      v0 = v // (10 ** 10)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 10) + p[0])
    return d
dij = dijkstra(N, e)
edij = dijkstra(N, e)
p = dij.path(s, 0)
revp = edij.path(t, 0)
mny = pow(10, 15)
table = [0] * (N + 1)
for x in range(1, N + 1):
  table[x] = mny - p[x] - revp[x]
csmx = [0] * (N + 1)
for i in range(N, 0, -1): csmx[i - 1] = max(csmx[i - 1], table[i], csmx[i])
for i in range(N): print(csmx[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, s, t = map(int, input().split())
e = dd(list)
for i in range(M):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  e[u + N].append((v + N, b))
  e[v + N].append((u + N, b))
for u in range(1, N + 1): e[u].append((u + N, 0))

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 10)
      v0 = v // (10 ** 10)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 10) + p[0])
    return d
dij = dijkstra(N * 2, e)
p = dij.path(s, t + N)
revp = dij.path(t + N, s)
mny = pow(10, 15)
table = [0] * (N + 1)
for x in range(1, N + 1):
  table[x] = mny - p[x] - revp[x + N]
csmx = [0] * (N + 1)
for i in range(N, 0, -1): csmx[i - 1] = max(csmx[i - 1], table[i], csmx[i])
for i in range(N): print(csmx[i])

Submission status: Wrong Answer

Solution code:
import heapq as hq
from collections import defaultdict
n, m, s, t = map(int,input().split())
s -= 1
t -= 1
edges = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edges[u-1].append((v-1, a, b))
    edges[v-1].append((u-1, a, b))
INF = float("inf")
d = [INF]*n
d[s] = 0
q = [(0,s)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, a, b in edges[i]:
        if d[j] > d[i]+a:
            d[j] = d[i]+a
            hq.heappush(q, (d[j], j))
ttoi = [INF]*n
ttoi[t] = 0
q = [(0,t)]
while q:
    dist, i = hq.heappop(q)
    if ttoi[i] < dist:
        continue
    for j, a, b in edges[i]:
        if ttoi[j] > ttoi[i]+b:
            ttoi[j] = ttoi[i]+b
            hq.heappush(q, (ttoi[j], j))
q = [(d[i]+ttoi[i], i+1) for i in range(n)]
hq.heapify(q)
i = 0
while i < n:
    x, j = hq.heappop(q)
    if i <= j-1:
        for _ in range(j-i):
            print(10**15-x)
        i = j-1
    i += 1

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s, neighbor):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, l in neighbor[v]:
            tmp_d = d + l
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    snuuk[u-1].append((v-1, b))
    snuuk[v-1].append((u-1, b))

dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
    if dist_s[i] + dist_t[i] < tmp:
        tmp = dist_s[i] + dist_t[i]
    ans[i] = 10 ** 15 - tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money)
snu = dijkstra(snu)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[s][j] + snu[j][t]))
    ans.append(ans_max)
for i in range(n,-1,-1):
    print(int(start - ans[i]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money)
snu = dijkstra(snu)
start = 10**15
#何年目か？
ans = []
ans_max = 0
for j in range(n,-1,-1):
    ans_max = max(ans_max, start - (money[s][j] + snu[j][t]))
    ans.append(ans_max)
for i in range(n,-1,-1):
    print(int(ans[i]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [set() for _ in range(n)]
eb = [set() for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].add((u,a))
    ea[u].add((v,a))
    eb[v].add((u,b))
    eb[u].add((v,b))


def dijkstra(e,n,s):
    INF = 10**9
    d = [INF]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

res.reverse()
for r in res:
    print(10**15 - r)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [set() for _ in range(n)]
eb = [set() for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].add((u,a))
    ea[u].add((v,a))
    eb[v].add((u,b))
    eb[u].add((v,b))


def dijkstra(e,n,s):
    INF = 10**9
    d = [INF]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d

res = []
m = None
for i in range(n-1,-1,-1):
    da = dijkstra(ea,n,s)
    db = dijkstra(eb,n,t)
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

res.reverse()
for r in res:
    print(10**15 - r)