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:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    # 頂点[ある始点からの最短距離]
    res = [INF] * N
    # スタート位置
    que = [src]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 距離*N + 現在のノード
        cur = heappop(que)
        # 距離とノードに分ける
        dist = cur // N
        cur %= N
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                # 距離*N+ノード番号 の形でキューに詰める
                heappush(que, (dist+cost)*N+nxt)
    # ノードsrcからの最短距離リストを返却
    return res

N, M, s, t = MAP()
s -= 1
t -= 1
nodes1 = tuple([] for i in range(N))
nodes2 = tuple([] for i in range(N))
for i in range(M):
    u, v, a, b = MAP()
    u -= 1
    v -= 1
    nodes1[u].append((v, a))
    nodes1[v].append((u, a))
    nodes2[u].append((v, b))
    nodes2[v].append((u, b))

res1 = dijkstra(N, nodes1, s)
res2 = dijkstra(N, nodes2, t)

A = [0] * N
for i in range(N):
    # sからiまで円、iからtまでスヌークで行く
    A[i] = res1[i] + res2[i]

# 最後のが使える両替所が少ないので、後ろから累積minする
ans = list(accumulate(A[::-1], min))[::-1]
total = 10 ** 15
[print(total-a) for a in ans]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import *

N, M, S, T = map(int, input().split())
INF = 10 ** 15
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for i 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):
    dist = [INF] * (N+1) # dist[0]使わない
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, p = heappop(que)
        # 既に安い交通費で来たことがある場合
        if dist[p] < d:
            continue
        for next_city, *fee in graph[p]:
            d1 = d + fee[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    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][1:]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
# D - Saving Snuuk
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N, M, S, T = map(int,input().split())
# graph[0]は使わない（都市の名前と添字が一致）
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v, a, b = map(int,input().split())
    # (v, a, b)はvの都市に行くのに、a円またはbスヌーク）
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    INF = 10 ** 15
    # 最初の所持金で初期化　dist[0]は使わない
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0,start)]
    while que:
        # (d, v) はdが現在の最小の交通費、vが現在の場所
        d, v = heappop(que)
        # 既に来たことがある場合、continue
        if dist[v] < d:
            continue
        for next_city, *fee in graph[v]:
            # modeによって円かスヌークを使うか選ぶ
            d1 = d + fee[mode]
            # 次の場所の交通費よりやすくなる場合は、データを更新
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

# 円だけで支払う場合、それぞれの都市にいくらで行けるか
d1 = np.array(dijkstra(S, 0))
# ゴール地点からスヌークで行く場合
d2 = np.array(dijkstra(T, 1))
# 足し合わせて、切り替わったところが両替地点
d1 += d2
# i年後、両替所がなくなった時、後ろから見ていった最小値
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N, M, S, T = map(int,input().split())
# graph[0]は使わない（都市の名前と添字が一致）
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v, a, b = map(int,input().split())
    # (v, a, b)はvの都市に行くのに、a円またはbスヌーク）
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    INF = 10 ** 15
    # 最初の所持金で初期化　dist[0]は使わない
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0,start)]
    while que:
        # (d, v) はdが現在の最小の交通費、vが現在の場所
        d, v = heappop(que)
        # 既に来たことがある場合、continue
        if dist[v] < d:
            continue
        for w, *a in graph[v]:
            # modeによって円かスヌー区を使うか選ぶ
            d1 = d + a[mode]
            # 次の場所の交通費よりやすくなる場合は、データを更新
            if dist[w] > d1:
                dist[w] = d1
                heappush(que, (d1, w))
    return dist

# 円で行く場合、それぞれの都市にいくらで行けるか
d1 = np.array(dijkstra(S, 0))
# ゴール地点からスヌークで行く場合
d2 = np.array(dijkstra(T, 1))
# 足し合わせて、切り替わったところが両替地点
d1 += d2
# i年後、両替所がなくなった時、後ろから見ていった最小値
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
 
 
class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))
 
    def dist(self, s, t):
        return self.val[t]
 
n, m, s, t = map(int, input().split())
en=Dijk(n)
snu=Dijk(n)
for i in range(m):
    a,b,c,d=map(int,input().split())
    en.add(a,b,c)
    en.add(b,a,c)
    snu.add(a,b,d)
    snu.add(b,a,d)
en.di(s)
snu.di(t)

mod=10**15
t=float('inf')
ans=[]
for i in range(n,0,-1):
    t=min(t,en.dist(s,i)+snu.dist(t,i))
    ans.append(mod-t)
for i in ans[::-1]:
    print(i)

Submission status: Accepted

Solution code:
from heapq import*
def dijkstra(s,e):
  g=10**6
  d=[10**18]*n
  f=[1]*n
  d[s]=f[s]=0
  q=[]
  for a,b in e[s]:heappush(q,a*g+b)
  while q:
    m=heappop(q)
    if f[m%g]<1:continue
    v=m%g
    x=d[v]=m//g
    f[v]=0
    for y,w in e[v]:
      if f[w]:heappush(q,(x+y)*g+w)
  return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)]
e,f=eval('[[]for _ in"_"*n],'*2)
for u,v,a,b in z:
  u-=1
  v-=1
  e[u]+=(a,v),
  e[v]+=(a,u),
  f[u]+=(b,v),
  f[v]+=(b,u),
a=[]
m=0
for y,s in zip(dijkstra(s-1,e)[::-1],dijkstra(t-1,f)[::-1]):
  m=max(m,10**15-y-s)
  a+=m,
print(*a[::-1])

Submission status: Accepted

Solution code:
from heapq import*
def dijkstra(n,s,edge):
    g=10**6
    d=[10**18]*n
    used=[True]*n
    d[s]=0
    used[s]=False
    edgelist=[]
    for a,b in edge[s]:heappush(edgelist,a*g+b)
    while edgelist:
        minedge=heappop(edgelist)
        if not used[minedge%g]:continue
        v1=minedge%g
        c1=d[v1]=minedge//g
        used[v1]=False
        for c2,v2 in edge[v1]:
            if used[v2]:heappush(edgelist,(c1+c2)*g+v2)
    return d
def main():
    n,m,s,t,*z=map(int,open(0).read().split())
    e1,e2=[[[]for _ in range(n)]for _ in range(2)]
    for u,v,a,b in zip(*[iter(z)]*4):
        u-=1
        v-=1
        e1[u]+=(a,v),
        e1[v]+=(a,u),
        e2[u]+=(b,v),
        e2[v]+=(b,u),
    c1=dijkstra(n,s-1,e1)
    c2=dijkstra(n,t-1,e2)
    a=[]
    m=0
    for y,s in zip(c1[::-1],c2[::-1]):
        t=10**15-y-s
        if t>m:m=t
        a+=m,
    print(*a[::-1],sep='\n')
main()

Submission status: Accepted

Solution code:
import heapq
from heapq import heapify, heappush, heappop

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)
  dist = [yen_dist[i]+snuuk_dist[i] for i in range(N)]
  for i in range(N-2, -1, -1):
    dist[i] = min(dist[i+1], dist[i])
  for i in range(N):
    print(10**15-dist[i])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import heapq
from heapq import heapify, heappush, heappop

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G, dist
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)
  #print(yen_dist)
  #print(snuuk_dist)
  dist = [yen_dist[i]+snuuk_dist[i] for i in range(N)]
  for i in range(N-2, -1, -1):
    dist[i] = min(dist[i+1], dist[i])
  for i in range(N):
    print(10**15-dist[i])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import heapq as h
n,m,s,t = map(int,input().split())
g = [dict() for _ in range(n+1)]
for _  in range(m):
  u,v,a,b = map(int,input().split())
  g[u][v] = (a,b)
  g[v][u] = (a,b)

def dijkstra(s,g,mode):
  dist = [10**15]*(n+1)
  seen = [False]*(n+1)
  dist[s] = 0
  q = [(0,s)]
  while q:
    d,v = h.heappop(q)
    if seen[v]:
      continue
    seen[v] = True
    dist[v] = d
    for x in g[v]:
      if not seen[x]:
        h.heappush(q,(dist[v]+g[v][x][mode],x))
  return dist

ou = dijkstra(s,g,0)
fuku = dijkstra(t,g,1)
rot = [(ou[i] + fuku[i],i) for i in range(n+1)]
h.heapify(rot)
for i in range(1,n+1):
  if rot[0][1] < i:
    while rot[0][1] < i:
      h.heappop(rot)
  print(10**15 - rot[0][0])

Submission status: Accepted

Solution code:
n, m, s, t = map(int,input().split())
s -= 1
t -= 1
# 円だけのグラフ
ad1 = [[] for _ in range(n)]
# スヌークだけのグラフ
ad2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int,input().split())
    u -= 1
    v -= 1
    ad1[u].append((v, a))
    ad1[v].append((u, a))
    ad2[u].append((v, b))
    ad2[v].append((u, b))

from heapq import heappush, heappop
inf = float('inf')

# 計算量O((E+V)logV)
# 引数(始点,隣接リスト)
def dijkstra(start,ad):
    #global cnt
    N = len(ad)
    dist = [inf] * N
    dist[start] = 0
    #cnt = [0] * N
    #cnt[start] = 1
    pq = [(dist[start], start)]
    while pq:
        dist_v, v = heappop(pq)
        for nv, nw in ad[v]:
            if dist[nv] > dist_v + nw:
                dist[nv] = dist_v + nw
                heappush(pq,(dist[nv], nv))
            #if dist[nv] == dist_v + nw:
                #cnt[nv] += cnt[v]
                #cnt[nv] %= mod
    return dist

dist1 = dijkstra(s, ad1)
dist2 = dijkstra(t, ad2)

ans_list = [inf]

for i in range(n)[::-1]:
    ans = min(ans_list[-1], dist1[i] + dist2[i])
    ans_list.append(ans)

ans_list.pop(0)
for ans in ans_list[::-1]:
    print(10**15-ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e, s, t = MAP()
s-= 1
t-= 1    
G1 = [[]for i in range(n)]
G2 = [[]for i in range(n)]       

for i in range(e):
    fr, to, w1, w2 = MAP()
    G1[fr-1].append((w1, to -1))
    G1[to-1].append((w1, fr -1))
    G2[fr-1].append((w2, to -1))
    G2[to-1].append((w2, fr -1))


def djkstra(s,G):
    visited = [False]*n     #その頂点を確定したかどうか
    d = [INF]*n
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s))

    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1]))
    
    return d

d_yen = djkstra(s,G1)
d_snuuk = djkstra(t,G2)

d_sum = [0]*n

for i in range(n):
    d_sum[i] = d_yen[i] + d_snuuk[i]

d_sum.reverse()
d_ans = [0]*n
d_ans[0] = d_sum[0]
for i in range(1,n):
    d_ans[i] = min(d_ans[i-1],d_sum[i])

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

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate
inf = float('inf')

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

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c
    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][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
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, -1)]

Submission status: Accepted

Solution code:
import heapq
n, m, s, t = map(int, input().split())
E = [[] for _ in range(n)]
A = [0] * m
B = [0] * m
for i in range(m):
  u, v, a, b = map(int, input().split())
  E[u - 1].append([v - 1, i])
  E[v - 1].append([u - 1, i])
  A[i] = a
  B[i] = b
L = [0] * n
Y = [10 ** 15] * n
S = [10 ** 15] * n
def dijkstra(s, D, W):
  Q = [[0, s]]
  D[s] = 0
  pos = 0
  while Q:
    d, q = heapq.heappop(Q)
    for adj, e in E[q]:
      if d + W[e] < D[adj]:
        D[adj] = d + W[e]
        pos += 1
        heapq.heappush(Q, [D[adj], adj])
  return D
dijkstra(s - 1, Y, A)
dijkstra(t - 1, S, B)
for i in range(n):
  L[i] = Y[i] + S[i]
for i in range(n - 2, -1, -1):
  L[i] = min(L[i + 1], L[i])
for i in range(n):
  print(10 ** 15 - L[i])

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

import heapq
class Heapq:
    def __init__(self, que=[], asc=True):
        if not asc:
            que = [-a for a in que]
        self.__que = que
        heapq.heapify(self.__que)
        self.__sign = 1 if asc else -1

    def pop(self):
        return heapq.heappop(self.__que) * self.__sign

    def push(self, value):
        heapq.heappush(self.__que, value * self.__sign)

    def pushpop(self, value):
        return heapq.heappushpop(self.__que, value * self.__sign) * self.__sign

    def top(self):
        return self.__que[0] * self.__sign

    def size(self):
        return len(self.__que)

def sol():
    N, M, start, end = map(int, input().split())
    start -= 1
    end -= 1
    edgeA = [[] for _ in range(N)]
    edgeB = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, a, b = map(int, input().split())
        fr -= 1
        to -= 1
        edgeA[fr].append((to, a))
        edgeA[to].append((fr, a))
        edgeB[fr].append((to, b))
        edgeB[to].append((fr, b))

    minDistA = [float('inf')] * N
    minDistB = [float('inf')] * N

    que = Heapq([])
    que.push((0, start))

    while que.size():
        dist, now = que.pop()

        if minDistA[now] <= dist:
            continue

        minDistA[now] = dist

        for to, cost in edgeA[now]:
            if minDistA[to] > dist + cost:
                que.push((cost + dist, to))

    que = Heapq([])
    que.push((0, end))

    while que.size():
        dist, now = que.pop()

        if minDistB[now] <= dist:
            continue

        minDistB[now] = dist

        for to, cost in edgeB[now]:
            if minDistB[to] > dist + cost:
                que.push((cost + dist, to))

    ans = [float('inf')] * (N + 1)
    for day in range(N)[:: -1]:
        newDist = minDistA[day] + minDistB[day]
        ans[day] = min(ans[day + 1], newDist)

    offset = 10**15
    for a in ans[: N]:
        print(offset - a)

sol()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF] * n
    visited = [False] * n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist

n, m, s, t = li()
s -= 1
t -= 1

yen_graph = [[] for _ in range(n)]
snk_graph = [[] for _ in range(n)]

for _ in range(m):
    u, v, a, b = li()
    u -= 1
    v -= 1

    yen_graph[u].append((v, a))
    yen_graph[v].append((u, a))
    snk_graph[u].append((v, b))
    snk_graph[v].append((u, b))

yen_dist = dijkstra(yen_graph, s)
snk_dist = dijkstra(snk_graph, t)

initial = 10**15

ans = [-1]*n
for i in range(n-1, -1, -1):
    if i == n-1:
        ans[i] = initial - (yen_dist[i] + snk_dist[i])

    else:
        ans[i] = max(ans[i+1], initial - (yen_dist[i] + snk_dist[i]))

for ansi in ans:
    print(ansi)

Submission status: Accepted

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

def djkstra(a,in_connect_list,v,money_kind):

    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(j[0])
        searching_list = new_search_list

    return out_shortest_list

n, m, s, t = [ int(v) for v in input().split() ]
connect_list = [ [] for i in range(n) ]

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


yen_list = djkstra(s-1,connect_list,n,1)
snuke_list = djkstra(t-1,connect_list,n,2)

remain_snule_list = [ 10**15 - yen_list[i] - snuke_list[i] for i in range(n) ][::-1]


for i in range(n-1):
    if remain_snule_list[i+1] < remain_snule_list[i]:
        remain_snule_list[i+1] = remain_snule_list[i]

remain_snule_list = remain_snule_list[::-1]

for i in remain_snule_list:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#SoundHound D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,s,t = LI()
graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = LI()
    graph1[u-1].append((v-1,a))
    graph1[v-1].append((u-1,a))
    graph2[u-1].append((v-1,b))
    graph2[v-1].append((u-1,b))

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

c1 = dijkstra(s-1,graph1)
c2 = dijkstra(t-1,graph2)
c = [c1[i] + c2[i] for i in range(n)]
money = 10**15
mi = c[-1]
for i in range(n-1)[::-1]:
    mi = min(mi,c[i])
    c[i] = mi
for i in range(n):
    print(money - c[i])

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)

Submission status: Accepted

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][1:]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

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][1:]

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

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

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

Submission status: Accepted

Solution code:

from collections import defaultdict
import heapq

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

    while len(check_num) > 0:
        now_dist, now_node = heapq.heappop(check_num)
        if dist_data[now_node] != -1:
            continue
        dist_data[now_node] = now_dist
        for next_node in graph_data[now_node]:
            if dist_data[next_node] != -1:
                continue
            heapq.heappush(check_num, (now_dist + weigh_data[(now_node, next_node)], next_node))

    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, start)
    knoke_dist = get_dikstra(graph_data, knoke_data, node_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()