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:
n,m,s,t=map(int,input().split())

import heapq
def dijkstra_heap(s,graph):
  #始点sから各頂点への最短距離と直前の点
  dist=[float("inf")]*size_v
  prev=[-1]*size_v
  used=[False]*size_v
  #used=set()
  dist[s]=0
  used[s]=True
  #used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
    #if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used[min_v]=True
    #used.add(min_v)
    for v,w in graph[min_v]:
      if not used[v]: 
      #if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

graph_yen=[[] for _ in range(n+1)]
graph_snu=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  graph_yen[u].append((v,a))
  graph_yen[v].append((u,a))
  graph_snu[u].append((v,b))
  graph_snu[v].append((u,b))
  
size_v=n+1
dist_yen,prev_yen=dijkstra_heap(s,graph_yen)
dist_snu,prev_snu=dijkstra_heap(t,graph_snu)
#print(dist_yen)
#print(dist_snu)

cost_list=[0]*(n+1)
cost_list[n]=dist_yen[n]+dist_snu[n]
for i in reversed(range(1,n)):
  cost_list[i]=min(cost_list[i+1],dist_yen[i]+dist_snu[i])
#print(cost_list)

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

Submission status: Accepted

Solution code:
from heapq import *
N,M,S,T=map(int,input().split())
S,T=S-1,T-1
u,v,a,b=0,0,0,0
Gy=[[] for i in range(N)]
Gs=[[] for i in range(N)]
for i in range(M):
  u,v,a,b=map(int,input().split())
  u,v=u-1,v-1
  Gy[v].append((u,a))
  Gy[u].append((v,a))
  Gs[v].append((u,b))
  Gs[u].append((v,b))
Dy=[0]*N
Ds=[0]*N
INF=10**15
def ijk(s,D,G):
  global INF
  for i in range(len(D)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S,Dy,Gy)
ijk(T,Ds,Gs)
Q=[Dy[i]+Ds[i] for i in range(N)]
P=[INF]
for i in range(N):
  P.append(min(P[i],Q[-i-1]))
for i in range(N):
  print(INF-P[-i-1])

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)

    class PQueueMin:
        '''
        min priority queue
        Attributes:
            self.pq (list): (priority, count, task) というタプルのエントリからなるヒープ。
            self.counter (iter): ユニークな番号。上記エントリを比較する際、task までに必ず順序関係が決定するようにするためのもの。(task に順序関係がないことがある)
        '''    
        def __init__(self):
            self.pq = []
            self.counter = count()

        def empty(self) -> bool:
            return len(self.pq) == 0

        def add_task(self, task: Any, priority: Num) -> None:
            count = next(self.counter)
            entry = (priority, count, task)
            heappush(self.pq, entry)
        
        def pop_task(self) -> Any:
            if self.empty():
                raise KeyError(f'PQueueMin.pop_task(): pqueue is empty.')
            priority, _, task = heappop(self.pq)
            return (task, priority)

        
    def dijkstra(adj_with_weight: Sequence[Sequence[int]], start: int=0) -> List[Num]:
        '''
        重みつき隣接リストを用いた Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [float('inf')] * V    # cost[i] = (minimum cost from node_start to node_i)
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        # 最初は始点が必ずコスト最小。pq に突っ込む
        pq.add_task(start, cost[start])
        while not pq.empty():
            # 現段階で最短のコストとなっている頂点を選択
            u, cost_of_u = pq.pop_task()
            if not fixed[u]:
                fixed[u] = True
                for v, weight_of_uv in adj_with_weight[u]:
                    if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                        cost[v] = cost_of_u + weight_of_uv
                        pq.add_task(v, cost[v])
        return cost
    

    n, m, s, t = mi()
    s -= 1
    t -= 1    
    adj_yen = [[] for _ in range(n)]
    adj_snuke = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj_yen[u].append((v, a))
        adj_yen[v].append((u, a))
        adj_snuke[u].append((v, b))
        adj_snuke[v].append((u, b))

    mincost_from_s_yen = dijkstra(adj_yen, start=s)
    mincost_from_t_snuke = dijkstra(adj_snuke, start=t)

    # debug(mincost_from_s_yen)
    # debug(mincost_from_t_snuke)

    rev_ans = []
    money = 10 ** 15
    prev = inf
    for i in range(n-1, -1, -1):
        # [i] 以降の都市は換金できる
        cost = mincost_from_s_yen[i] + mincost_from_t_snuke[i]
        prev = min(cost, prev)
        rev_ans.append(money - prev)
    
    for elm in reversed(rev_ans):
        print(elm)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
N, M, S, T = map(int, input().split())
S,T = S-1, T-1 # 0-indexed
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
inf = 10**18

for i in range(M):
  u,v,a,b = map(int, input().split())
  u,v = u-1, v-1
  A[u].append((v,a))
  A[v].append((u,a))
  B[u].append((v,b))
  B[v].append((u,b))
  
def dij(D, parent):
  fixed = [ False for _ in range(N)]
  ret = [ 10**18 for _ in range(N)]
  h = []
  heapq.heappush(h, (0,parent))
  while h:
    d, now = heapq.heappop(h)
    if fixed[now]:
      continue
    fixed[now] = True
    ret[now] = d
    for nxt, cost in D[now]:
      if fixed[nxt]:
        continue
      heapq.heappush(h, (d+cost, nxt))
  return ret
  
DA = dij(A, S)
DB = dij(B, T)

ANS = [ 0 for _ in range(N+1) ]
ANS[N] = inf
for i in range(N-1,-1,-1):
  ANS[i] = min(ANS[i+1], DA[i] + DB[i])
  
for i in range(N):
  print(10**15 - ANS[i])

#print(DA)
#print(DB)
"""
aのネットワークと、bのネットワーク別々に作って、SからTの最短距離を出す
n-1年目から1年目に遡っていく形で最短を出していく。
A[S][T] と A[S][N-1] + B[N-1][T]を比較すれば良い
"""

Submission status: Accepted

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

# 各都市に対して、
# (1)Sから到達したときの円貨の最小値
# (2)Gから到達したときのスヌークの最小値
# をダイクストラで求める。
# 各都市で両替したときのコストは、(1)と(2)の和である。
# 年を逆順に遡って、順に両替所が開設されると仮定する。
# 新規に開設された(1)と(2)の和が最小値を更新するようであれば更新。最小値がその年の答え。
# コストは最大でも(10 ** (9 + 5)) * 2程度であるため、所持金は超えない。最後に引けばOK。

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

INF = 10 ** 15

import heapq as hq
# ダイクストラ
# グラフ, 取るべきコストのindex(円:1, スヌーク:2), 開始点
def get_min_cost(G, label, start):
  dist_from_start = [INF] * len(G)
  # そこまでのコスト, 頂点, 親
  q = [(0, start, -1)]
  hq.heapify(q)
  while q:
    cost, v, parent = hq.heappop(q)
    if dist_from_start[v] <= cost:
      continue
    dist_from_start[v] = cost
    for child in G[v]:
      if child[0] == parent:
        continue
      hq.heappush(q, (dist_from_start[v] + child[label], child[0], v))
  return dist_from_start
  
dist_from_s = get_min_cost(G, 1, S - 1)
dist_from_g = get_min_cost(G, 2, T - 1)

best = INF
ans = [0] * N
wallet = 10 ** 15
for i in range(N - 1, -1, -1):
  # 逆順に両替所を更新していく
  if dist_from_s[i] + dist_from_g[i] < best:
    best = dist_from_s[i] + dist_from_g[i]
  ans[i] = wallet - best

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,s,t = list(map(int, input().split()))
s -= 1
t -= 1
from collections import defaultdict
ns1 = defaultdict(set)
ns2 = defaultdict(set)
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u -= 1
    v -= 1
    ns1[u].add((a,v))
    ns1[v].add((a,u))
    ns2[u].add((b,v))
    ns2[v].add((b,u))

def dijkstra(ns, start):
    import heapq
    vals = [None] * n
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
d1 = dijkstra(ns1, s)
d2 = dijkstra(ns2, t)
ds = [None]*n
for i in range(n):
    ds[i] = d1[i] + d2[i]
for i in range(n-2, -1, -1):
    ds[i] = min(ds[i], ds[i+1])
base = pow(10,15)
write("\n".join(map(lambda x: str(base-x), ds)))

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
s,t=s-1,t-1
g=[[] for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u,v=u-1,v-1
  g[u].append([v,a,b])
  g[v].append([u,a,b])
inf=float('inf')
froms=[inf]*n
froms[s]=0
fromt=[inf]*n
fromt[t]=0
from heapq import heappop,heappush
ka=set(())
todo=[[0,s]]
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  ka.add(v)
  for nv,nd,_ in g[v]:
    if froms[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      froms[nv]=d+nd
ka=set(())
todo=[[0,t]]
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  ka.add(v)
  for nv,_,nd in g[v]:
    if fromt[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      fromt[nv]=d+nd
pay=[[i,froms[i]+fromt[i]] for i in range(n)]
pay.sort(key=lambda x:x[1],reverse=True)
for i in range(n):
  while pay[-1][0]<i:
    pay.pop()
  print(pow(10,15)-pay[-1][1])

Submission status: Accepted

Solution code:
import heapq
n, m, s, t = map(int, input().split())
node = [False] * n # 訪問済み
gyen = [[] for i in range(n)]
gsnu = [[] for i in range(n)]

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

distyen = [float('inf')] * n
distsnu = [float('inf')] * n

# yenのダイクストラ、sから
distyen[s-1] = 0
node[s-1] = True
q = []
for e in gyen[s-1]:
    heapq.heappush(q, e)

while q:
    cost, v = heapq.heappop(q)
    if node[v]:
        continue
    node[v] = True
    distyen[v] = cost
    for e in gyen[v]:
        nextcost, to = e
        heapq.heappush(q, (cost+nextcost, to))

node = [False] * n
distsnu[t-1] = 0
node[t-1] = True
q = []
for e in gsnu[t-1]:
    heapq.heappush(q, e)
while q:
    cost, v = heapq.heappop(q)
    if node[v]:
        continue
    distsnu[v] = cost
    node[v] = True
    for e in gsnu[v]:
        nextcost, to = e
        heapq.heappush(q, (cost+nextcost, to))

ans = []
for i in range(n-1, -1, -1):
    if i == n-1:
        ans.append(pow(10, 15) - distyen[i] - distsnu[i])
    else:
        ans.append(max(ans[-1], pow(10, 15) - distyen[i] - distsnu[i]))
for i in ans[::-1]:
    print(i)

Submission status: Accepted

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

from heapq import heappop, heappush
inf = 10 ** 15
cost_a = [inf] * n
cost_a[s] = 0
que = [(cost_a[s], s)]
while que:
    cost, cur = heappop(que)
    if cost > cost_a[cur]:
        continue
    for to, a, _ in edges[cur]:
        if cost_a[to] > cost + a:
            cost_a[to] = cost + a
            heappush(que, (cost_a[to], to))

cost_b = [inf] * n
cost_b[t] = 0
que = [(cost_b[t], t)]
while que:
    cost, cur = heappop(que)
    if cost > cost_b[cur]:
        continue
    for to, _, b in edges[cur]:
        if cost_b[to] > cost + b:
            cost_b[to] = cost + b
            heappush(que, (cost_b[to], to))

ans = [10 ** 15]
for i in range(n-1, -1, -1):
    ans.append(min(ans[-1], cost_a[i] + cost_b[i]))
for i in range(1, n+1):
    print(10 ** 15 - ans[-i])

Submission status: Accepted

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

import heapq

def dijkstra(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m,s,t=map(int,input().split())
s,t=s-1,t-1
edge1=[[] for _ in range(n)]
edge2=[[] for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  edge1[u-1].append([a,v-1])
  edge1[v-1].append([a,u-1])
  edge2[u-1].append([b,v-1])
  edge2[v-1].append([b,u-1])
d1=dijkstra(s,edge1)
d2=dijkstra(t,edge2)
INF=10**15
ans=[INF]*n
ans[n-1]=int(d1[n-1]+d2[n-1])
for i in range(n-2,-1,-1):
  tmp=int(d1[i]+d2[i])
  ans[i]=min(tmp,ans[i+1])
for i in range(n):
  print(INF-ans[i])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():


    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**16
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    
    N,M,s,t=MI()
    s-=1
    t-=1
    djk=Dijkstra(N)
    djk2=Dijkstra(N)
    
    for _ in range(M):
        u,v,a,b,=MI()
        u-=1
        v-=1
        djk.add2(u,v,a)
        djk2.add2(u,v,b)
        
    #sから何円かかるか，tから何すヌークかかるか
    Ds=djk.shortest_path(s)
    Dt=djk2.shortest_path(t)
    
    #iで換金する時のコスト
    cost=[0]*N
    for i in range(N):
        cost[i]=Ds[i]+Dt[i]
        
    mon=10**15
    ans=[0]*N
    temp=0
    for i in range(N-1,-1,-1):
        ans[i]=max(temp,mon-cost[i])
        temp=ans[i]
        
    for i in range(N):
        print(ans[i])
    
    
    

main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

import heapq

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

edges = [[] for i in range(N)]
edget = [[] for i in range(N)]

for i in range(M):
    u,v,a,b = map(int,readline().split())
    u -= 1
    v -= 1
    edges[u].append([a,v])
    edges[v].append([a,u])
    edget[u].append([b,v])
    edget[v].append([b,u])

def dijkstra_heap(s,n,edge):
    #始点sから各頂点への最短距離
    d = [INF] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

ds = dijkstra_heap(S-1,N,edges)
dt = dijkstra_heap(T-1,N,edget)

ans = [INF]*N
ans[0] = ds[N-1] + dt[N-1]
for i in range(1,N):
    ans[i] = min(ans[i-1],ds[N-i-1]+dt[N-i-1])
for i in range(N):
    print(10**15-ans[N-1-i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import accumulate
n,m,s,t= map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]

g = defaultdict(list)
c = {}
'''
for i in range(1,n+1):
    g[i].append(n+i)
    c[(i,n+i)] = 0
    '''
for u,v,a,b in uvab:
    g[u].append(v)
    g[v].append(u)
    g[n+u].append(n+v)
    g[n+v].append(n+u)
    c[(u,v)] = a
    c[(v,u)] = a
    c[(n+u,n+v)] = b
    c[(n+v,n+u)] = b

inf = 10**15
ds2t = [inf for i in range(2*n+1)]
ds2t[s] = 0

dq = deque([s])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if ds2t[nv] > ds2t[v] + c[(v,nv)]:
            ds2t[nv] = ds2t[v] + c[(v,nv)]
            dq.append(nv)


dt2s = [inf for i in range(2*n+1)]
dt2s[n+t] = 0

dq = deque([n+t])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if dt2s[nv] > dt2s[v] + c[(v,nv)]:
            dt2s[nv] = dt2s[v] + c[(v,nv)]
            dq.append(nv)

ds = []
for i in range(1,n+1):
    ds.append(ds2t[i] + dt2s[n+i])

ds = accumulate(ds[::-1], min)

for d in reversed(list(ds)): 
    print(10**15-d)

Submission status: Accepted

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)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    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: Accepted

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

def dijkstra(G, sta):
    dist = [10**18]*n
    dist[sta] = 0
    pq = []
    heappush(pq, (0, sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

n, m, s, t = map(int, input().split())
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    G1[u-1].append((v-1, a))
    G1[v-1].append((u-1, a))
    G2[u-1].append((v-1, b))
    G2[v-1].append((u-1, b))

d1 = dijkstra(G1, s-1)
d2 = dijkstra(G2, t-1)
ans = [0]

for i in range(n-1, -1, -1):
    ans.append(max(ans[-1], 10**15-d1[i]-d2[i]))

ans.reverse()

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

Submission status: Accepted

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    n,m,s,t=map(int,input().split())
    yedge=[[]for i in range(n+1)]
    sedge=[[]for i in range(n+1)]
    for i in inputs():
        fro,to,cy,cs=map(int,i.split())
        yedge[fro].append((to,cy))
        yedge[to].append((fro,cy))
        sedge[fro].append((to,cs))
        sedge[to].append((fro,cs))
    from heapq import  heappop, heappush
    def dijkstra(edges,start):
        #edges->edges[from]=[(to,cost)]
        #1-based-index->|edges|=n+1
        #return ->distance(no path, then -1)
        d=[-1]*len(edges)
        #fr=[[]for i in range(len(edges))]
        hq=[(0,start)]
        while hq:
            c,v=heappop(hq)
            if d[v]!=-1:continue
            d[v]=c
            #fr[v]=f
            for to,cos in edges[v]:
                if d[to]==-1:heappush(hq,(c+cos,to))
        return d#,fr
    yd=dijkstra(yedge,s)
    sd=dijkstra(sedge,t)
    ret=[]
    ans=0
    k=10**15
    for i in range(n,0,-1):
        ans=max(ans,k-yd[i]-sd[i])
        ret.append(ans)
    ret.reverse()
    print(*ret,sep="\n")
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        prev = [None for _ in range(self.n)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    prev[adj] = node
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

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

E1 = []
E2 = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    E1.append((u, v, a))
    E2.append((u, v, b))
    
g1 = Graph(N, E1)
g2 = Graph(N, E2)
dist_from_s = g1.dijkstra(S - 1)
dist_from_t = g2.dijkstra(T - 1)

res = list()
tmp = 0

for i in range(N)[::-1]:
    tmp = max(tmp, 10**15 - dist_from_t[i] - dist_from_s[i])
    res.append(tmp)
    
print('\n'.join(map(str, res[::-1])))

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    cost[s] = 0
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
                cost[u] = c + d
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
res = [-1] * n
tmp = 10 ** 16
for i in range(n-1, -1, -1):
    if py[i] + ps[i] < tmp:
        tmp = py[i] + ps[i]
    res[i] = 10 ** 15 - tmp
print(*res, sep='\n')