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: Accepted

Solution code:
import heapq
import sys
from itertools import accumulate

n,m,s,t = map(int,next(sys.stdin).split(" "))
inf = 1000000000000000
gyen = [dict() for _ in range(n)]
gsnuk = [dict() for _ in range(n)]

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

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

yen = dijkstra(gyen,s-1)
snuke = dijkstra(gsnuk,t-1)

ans = list(accumulate([y+s for y,s in zip(yen,snuke)][::-1],min))
[print(inf-ans[i]) for i in range(n-1,-1,-1)]

Submission status: Accepted

Solution code:
from heapq import *

INF = 10**15

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


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))

S = [INF]*V
T = [INF]*V
djikstra(Ga,s-1,S)
djikstra(Gb,t-1,T)
M = [0]*n
for i in range(n):
    M[i] = INF-S[i]-T[i]
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: Accepted

Solution code:
from heapq import *
from numpy import array
INF = 10**15

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


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))

S = [INF]*V
T = [INF]*V
djikstra(Ga,s-1,S)
djikstra(Gb,t-1,T)

M = INF-(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: Accepted

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


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            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))

S = djikstra(Ga,s-1)

T = djikstra(Gb,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: Accepted

Solution code:
import heapq

INF = 100000000000000000000
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
aa = [[] for _ in range(n)]
bb = [[] for _ in range(n)]

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


def dijkstra(graph, s, mins):
    heap = []
    heapq.heappush(heap, (0, s))
    mins[s] = 0
    visited = [False] * n
    while len(heap) > 0:
        cost, cur = heapq.heappop(heap)
        if visited[cur]:
            continue
        visited[cur] = True
        for c, i in graph[cur]:
            if visited[i]:
                continue
            if mins[i] > cost + c:
                mins[i] = cost + c
                heapq.heappush(heap, (cost + c, i))

mins_a = [INF] * n
dijkstra(aa, s, mins_a)
mins_b = [INF] * n
dijkstra(bb, t, mins_b)
maxs = [0] * n
for i in range(n):
    maxs[i] = 1000000000000000 - (mins_a[i] + mins_b[i])
ans = [0] * n
ans[n - 1] = maxs[n - 1]
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], maxs[i])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import heapq

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

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

def Digkstra(Cost_dict, start):   
    dist = [float('inf') for _ in range(n)]
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest, cost in Cost_dict[src]:
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
    return dist

Yen_dist = Digkstra(Yen_cost, s-1)
Snuuk_dist = Digkstra(Snuuk_cost, t-1)

First = 10**15
Money = []
Money.append(int(First - Yen_dist[-1] - Snuuk_dist[-1]))
for year in range(n-2, -1, -1):
    temp = First - Yen_dist[year] - Snuuk_dist[year]
    if temp > Money[-1]:
        Money.append(temp)
    else:
        Money.append(Money[-1])

for i in range(n):
    print(Money[-1-i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# 
vertices = []
for i in range(n):
  v = []
  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].append([v-1, a, b])
    vertices[v-1].append([u-1, a, b])


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

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

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in vertices[v]:
        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_pre = [inf] * n
    dist = [inf] * n
    h = []
    heappush(h, (0, s))
    dist_pre[s] = 0
    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(v)
        #print(v, list_adj)
        for adj in list_adj:
            if dist[adj[0]] == inf:
                dnew = dv + adj[1]
                if dnew < dist_pre[adj[0]]:
                    dist_pre[adj[0]] = dnew
                    heappush(h, (dnew, adj[0]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
cost = [a+b for a, b in zip(dist_a, dist_b)]
#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(dist_a)
#print(dist_b)
#print(cost)
#cost = np.array(cost, dtype='int')

res = [0]*n

min_temp = int(1e20)
m0 = int(1e15)
for i in range(n):
    k = n-1-i
    if(cost[k]<min_temp):
        min_temp = cost[k]
    res[k] = m0 - min_temp
    #cost_available = cost[i:]
    #print(m0-np.amin(cost_available))

for r in res:
    print(r)

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])

Submission status: Accepted

Solution code:
import sys
import heapq
import operator as op
from itertools import accumulate

inf = float("inf")

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

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

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

    return dist, prev

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

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

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

yen, _ = dijkstra(yen_graph, s-1)
snuke, _ = dijkstra(snuke_graph, t-1)
result = list(accumulate([y+s for y, s in zip(yen, snuke)][::-1], min))

for i in range(n-1, -1, -1):
    print(10**15 - result[i])

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from itertools import accumulate
 
def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float("inf")):
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1
 
    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1
 
        dests = ((i, n) for i, n in enumerate(edges[v]) if n != default_value)\
            if adj_matrix else edges[v]
 
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))
 
    return vertices
 
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen = [[] for _ in [0]*n]
sno = [[] for _ in [0]*n]
for l in sys.stdin.readlines():
    u, v, a, b = map(int, l.strip().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    sno[u-1].append((v-1, b))
    sno[v-1].append((u-1, b))
 
yen = dijkstra(n, yen, s)
sno = dijkstra(n, sno, t)
result = list(accumulate([y+s for y, s in zip(yen, sno)][::-1], min))
money = 10**15
for n in result[::-1]:
    print(money-n)

Submission status: Accepted

Solution code:
from itertools import accumulate
import heapq
n,m,s,t=map(int, input().split())
s-=1
t-=1
yen=[{} for _ in range(n)]
snk=[{} for _ in range(n)]
for _ in range(m):
    u,v,a,b=map(int, input().split())
    u-=1    
    v-=1    
    yen[u][v]=a
    yen[v][u]=a
    snk[u][v]=b
    snk[v][u]=b
 
def dijkstra(s, t, g):
    q=[]
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(q, (d[s], s))
    while q!=[]:
        du, u=heapq.heappop(q)
        if du>d[u]:
            continue
        for v in g[u]:
            if d[v]>du+g[u][v]:
                d[v]=du+g[u][v]
                heapq.heappush(q, (d[v], v))
    return d
 
d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
ans=list(accumulate(reversed([y+s for y,s in zip(d1, d2)]), min))
for ai in reversed(ans):
    print(10**15-ai)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate
import heapq
n,m,s,t=map(int, input().split())
s-=1
t-=1
yen={}
snk={}
adj=defaultdict(list)
for _ in range(m):
    u,v,a,b=map(int, input().split())
    u-=1    
    v-=1    
    adj[u].append(v)
    adj[v].append(u)
    yen[u,v]=a
    yen[v,u]=a
    snk[u,v]=b
    snk[v,u]=b
 
def dijkstra(s, t, cost):
    q=[]
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(q, (d[s], s))
    while q!=[]:
        du, u=heapq.heappop(q)
        if du>d[u]:
            continue
        for v in adj[u]:
            if d[v]>du+cost[u,v]:
                d[v]=du+cost[u,v]
                heapq.heappush(q, (d[v], v))
    return d
 
d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
ans=list(accumulate(reversed([y+s for y,s in zip(d1, d2)]), min))
for ai in reversed(ans):
    print(10**15-ai)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

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

    hq = [(0, v)]

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

    return d

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate

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

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

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

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

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

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

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate

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

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

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

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

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

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

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

Submission status: Accepted

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]*(N+1)
i = 0
for yen, snk in zip(dist_yen[::-1], dist_snk[::-1]):
    i+=1
    min_after_i = yen+snk
    min_list[i] = min(min_after_i,min_list[i-1])

del min_list[0]

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

Submission status: Accepted

Solution code:
import heapq
n,m,s,t=map(int,input().split())
s-=1
t-=1
Gyen=[dict() for i in range(n)]
Gsnu=[dict() for i in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    Gyen[u][v]=a
    Gyen[v][u]=a
    Gsnu[u][v]=b
    Gsnu[v][u]=b
def dijkstra(adj, start):
    num = n          # グラフのノード数
    dist = [10**15 for i in range(num)] # 始点から各頂点までの最短距離を格納する
   
    dist[start] = 0
    q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    heapq.heappush(q, (0, start)) # 始点をpush
    while (len(q) != 0):
        prov_cost, src = heapq.heappop(q) # pop
        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue
        # 他の頂点の探索
        for dest in adj[src]:
            cost = adj[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost # distの更新
                heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush                  
    return dist
CostYen=dijkstra(Gyen,s)
CostSnu=dijkstra(Gsnu,t)
Cost=[0 for i in range(n)]
for i in range(n):
    Cost[i]=CostYen[i]+CostSnu[i]
ans=[0 for i in range(n)]
ans[-1]=Cost[-1]
for i in list(range(n-1))[::-1]:
    ans[i]=min(ans[i+1],Cost[i])
for i in range(n):
    print(10**15-ans[i])

Submission status: Accepted

Solution code:
import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    su.append([x1-1,y1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
 
 
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
snuke=[]
for d1i, d2i in zip(d1,d2):
    snuke.append(d1i+d2i)
ans=[]
mins=float('inf')
for si in reversed(snuke):
    if si<mins:
        ans.append(si)
        mins=si
    else:
        ans.append(mins)
ans.reverse()
for ai in ans:
    print(10**15-ai)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


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

# faster #####################################################################
yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

# slower ####################################################################
# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for l in sys.stdin.readlines():
#     u, v, yen, snuke = map(int, l.strip().split())
#     yen_edges[u - 1][v - 1] = yen
#     yen_edges[v - 1][u - 1] = yen
#     snuke_edges[u - 1][v - 1] = snuke
#     snuke_edges[v - 1][u - 1] = snuke

# yen_costs = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_costs = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)

final_costs = list(
    accumulate([yen + snuke
                for yen, snuke in zip(yen_costs, snuke_costs)][::-1],
               min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)