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:
from heapq import heappush, heappop

INF = float("inf")
def dijkstra(E, r):
    D = [INF] * len(E)
    D[r] = 0

    Q = [(0, r)]
    while Q:
        dist, cur = heappop(Q)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, (cand, nxt))

    return D


N, M, S, T, *UVAB = map(int, open(0).read().split())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A[u].append((v, a))
    A[v].append((u, a))
    B[u].append((v, b))
    B[v].append((u, b))

A = dijkstra(A, S)
B = dijkstra(B, T)

init = 10 ** 15

ans = []
cur = INF
for a, b in zip(reversed(A[1:]), reversed(B[1:])):
    cur = min(cur, a + b)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[[] for i in range(N)] for _ in range(2)]
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  graph[0][u].append((v, a)); graph[0][v].append((u, a))
  graph[1][u].append((v, b)); graph[1][v].append((u, b))


def dijkstra(s, mode):
  dist = [-1] * N
  dist[s] = 0
  e = []
  for child, cost in graph[mode][s]:
    heappush(e, (cost, child))
  while e:
    cost, node = heappop(e)
    if dist[node] >= 0:
      continue
    dist[node] = cost
    for child, c in graph[mode][node]:
      if dist[child] >= 0:
        continue
      heappush(e, (cost+c, child))
  return dist
  
dist = [dijkstra(s, 0), dijkstra(t, 1)]  
value = [dist[0][i]+dist[1][i] for i in range(N)]

ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[[] for i in range(N)] for _ in range(2)]
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  graph[0][u].append((v, a)); graph[0][v].append((u, a))
  graph[1][u].append((v, b)); graph[1][v].append((u, b))


def dijkstra(s, mode):
  dist = [-1] * N
  dist[s] = 0
  e = []
  for child, cost in graph[mode][s]:
    heappush(e, (cost, child))
  while e:
    cost, node = heappop(e)
    if dist[node] >= 0:
      continue
    dist[node] = cost
    for child, c in graph[mode][node]:
      if dist[child] >= 0:
        continue
      heappush(e, (cost+c, child))
  return dist
  
dist = [dijkstra(s, 0), dijkstra(t, 1)]  
value = [dist[0][i]+dist[1][i] for i in range(N)]

ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

Submission status: Accepted

Solution code:
import heapq
N,m,S,T = map(int,input().split())
S -= 1
T -= 1
adj_yen = [ [] for _ in range(N) ]
adj_snk = [ [] for _ in range(N) ]

for _ in range(m):
  u,v,y,sn = map(int,input().split())
  u -= 1
  v -= 1
  adj_yen[u].append((v,y))
  adj_yen[v].append((u,y))

  adj_snk[u].append((v,sn))
  adj_snk[v].append((u,sn))

def dijkstra(g,s):
  costs = [float("inf")] * N
  costs[s] = 0
  visited = [False] * N

  q = [(0,s)]
  while q:
    c,n = heapq.heappop(q)
    if visited[n]: continue
    visited[n] = True

    for nei, nc in g[n]:
      if nc+c < costs[nei]:
        costs[nei] = nc+c
        heapq.heappush(q, (nc+c,nei))
  return costs

costs_yen = dijkstra(adj_yen, S)
costs_snk = dijkstra(adj_snk, T)

cur_year = N-1
prev_cost = 10**15
res = [0] * N
while cur_year >= 0:
  tot = costs_yen[cur_year] + costs_snk[cur_year]
  res[cur_year] = 10**15 - min(prev_cost, tot)
  prev_cost = min(prev_cost, tot)
  cur_year -= 1

for r in res:
  print(r)

Submission status: Accepted

Solution code:
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
def main():
    import sys
    input = sys.stdin.readline
    import heapq
    n,m,s,t = map(int,input().split())
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))

    yenEdges = [[] for _ in range(n+1)]
    snuukEdges = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        yenEdges[u].append((v,a))
        yenEdges[v].append((u,a))
        snuukEdges[u].append((v,b))
        snuukEdges[v].append((u,b))
    yenDic = {}
    snuukDic = {}

    dijkstra(yenEdges,yenDic,s)
    dijkstra(snuukEdges,snuukDic,t)

    remainingSnuuk = []
    for i in range(1,n+1):
        remainingSnuuk.append((10**15-(yenDic[i]+snuukDic[i]),i))
    remainingSnuuk.sort(key=lambda x: x[0], reverse=True)

    j = 0
    for i in range(n):
        while remainingSnuuk[j][1] <= i:
            j += 1
        print(remainingSnuuk[j][0])
main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue # 距離が最小でない場合は飛ばす
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

n,m,s,t=map(int,input().split())
Gs=[[] for i in range(n)]
Gt=[[] for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  Gs[u-1].append([v-1,a])
  Gs[v-1].append([u-1,a])
  Gt[u-1].append([v-1,b])
  Gt[v-1].append([u-1,b])
s-=1
t-=1
yen=dijkstra(s,n,Gs)
snk=dijkstra(t,n,Gt)
cost=[10**15-(yen[i]+snk[i]) for i in range(n)]
for i in range(n-2,-1,-1):
  cost[i]=max(cost[i],cost[i+1])
for c in cost:
  print(c)

Submission status: Accepted

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

n,m,s,t = map(int,input().split())
pathy = [{} for _ in range(n)]
paths = [{} for _ in range(n)]

import heapq
def Dijkstra(edge,start,v):
    d = [float('inf')]*v
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        if dist > d[p]:continue
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

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

dy = Dijkstra(pathy,s-1,n)
ds = Dijkstra(paths,t-1,n)
ans = [0]*n
for i in range(n)[::-1]:
    if i == n-1:
        ans[i] = dy[i] + ds[i]
    else:
        ans[i] = min(ans[i+1], dy[i]+ds[i])
print('\n'.join(str(10**15 - i) for i in ans))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 有向グラフで優先度付きキューで探索

from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')

def dijkstra(s,n,g):
    seen = [False]*n
    cost = [INF]*n
    cost[s] = 0 #スタートはコスト0
    next_q = [(0,s)]
    heapify(next_q)
    while len(next_q)>0:
        c, i = heappop(next_q)
        if cost[i] < c:
            continue
        for nedge, ncost in g[i]:
            nc = cost[i]+ncost
            if cost[nedge]>nc:
                cost[nedge] = nc
                heappush(next_q,(nc, nedge))
    return cost

def main():
    N, M, S, T = map(int, input().split())
    graph_F = [[] for _ in range(N)]
    graph_R = [[] for _ in range(N)]
    #リストの作成
    for i in range(M):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        graph_F[a].append((b,c))
        graph_F[b].append((a,c))
        graph_R[a].append((b,d))
        graph_R[b].append((a,d))

    F = dijkstra(S-1,N,graph_F)
    R = dijkstra(T-1,N,graph_R)

    ret = [i+j for (i, j) in zip(F, R)]
    X = 10**15
    for r in range(N-2,-1,-1):
        ret[r] = min(ret[r+1], ret[r])
    for r in ret:
        print(X-r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    n,m,s,t = LI()
    y_root = [[] for _ in range(n)]
    s_root = [[] for _ in range(n)]
    y_node = [INF] * n
    s_node = [INF] * n
    for _ in range(m):
        u,v,a,b = LI()
        y_root[u-1].append((v-1,a))
        y_root[v-1].append((u-1,a))
        s_root[u-1].append((v-1,b))
        s_root[v-1].append((u-1,b))

    def dist(node,root,r):
        q = [(0,r)]
        heapify(q)
        node[r] = 0
        while q:
            d,u = heappop(q)
            if node[u] < d: continue
            for v,e in root[u]:
                if d+e < node[v]:
                    node[v] = d+e
                    heappush(q,(d+e,v))

    dist(y_node,y_root,s-1)
    dist(s_node,s_root,t-1)

    t_node = [(y_node[i] + s_node[i],i) for i in range(n)]
    t_node.sort()

    p = 0
    for i in range(n):
        while t_node[p][1] < i:
            p += 1
        print(10**15 - t_node[p][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N,M,S,T = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = map(int, input().split())
    E[u-1].append((v-1, a, b))
    E[v-1].append((u-1, a, b))

def dijkstra(s, n):
    inf = 10**18
    d = [inf]*N
    d[s] = 0
    h = []
    used = [0]*N
    used[s] = 1
    for e in E[s]:
        heapq.heappush(h, (e[n], e[0]))
    while h:
        temp = heapq.heappop(h)
        r = temp[0]
        u = temp[1]
        if used[u] == 1:
            continue
        d[u] = r
        used[u] = 1
        for e in E[u]:
            if used[e[0]] == 1:
                continue
            heapq.heappush(h, (r+e[n], e[0]))
    return d

money = 10**15
A = dijkstra(S-1, 1)
B = dijkstra(T-1, 2)
ans = [0]*(N+1)

for i in range(N-1, -1, -1):
    ans[i] = max(ans[i+1], money-A[i]-B[i])
    
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

show_flg=False
show_flg=True
ans=0



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

A=[]
B=[]
for i in range(m):
    u,v,a,b=LI_()
    A+=[(u,v,a+1)]
    B+=[(u,v,b+1)]

ga,_=GI(n,m,A,index=0)
da,_=dijkstra(ga,s)

gb,_=GI(n,m,B,index=0)
db,_=dijkstra(gb,t)

c=[da[i]+db[i] for i in range(n)]

m=inf
ans=[]
for i in range(n)[::-1]:
    m=min(c[i],m)
    ans.append(10**15-m)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import heapq
def dijkstra(s,graph,n):
    dist=[float("inf") for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,s))
    while pq:
        mini_dis,node=heapq.heappop(pq)
        if dist[node]<mini_dis: continue
        for w,point in graph[node]:
            if dist[point]<w:continue
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    return dist
N,M,S,T=map(int,input().split())
graph_yen=[[] for i in range(N+1)]
graph_snuke=[[] for i in range(N+1)]
for _ in range(M):
    u,v,a,b=map(int,input().split())
    graph_yen[u].append((a,v))
    graph_yen[v].append((a,u))
    graph_snuke[u].append((b,v))
    graph_snuke[v].append((b,u))
    
yen=dijkstra(S,graph_yen,N)
snuke=dijkstra(T,graph_snuke,N)
minimum_case=[10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i]-=(yen[i+1]+snuke[i+1])
for i in range(N-1,-1,-1):
    minimum_case[i]=max(minimum_case[i],minimum_case[i+1])
for i in range(1,N+1):
    print(minimum_case[i])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import heapq
def dijkstra(s,graph,n):
    dist=[float("inf") for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,s))
    while pq:
        mini_dis,node=heapq.heappop(pq)
        if dist[node]<mini_dis: continue
        for w,point in graph[node]:
            if dist[point]<w:continue
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    return dist
N,M,S,T=map(int,input().split())
graph_yen=[[] for i in range(N+1)]
graph_snuke=[[] for i in range(N+1)]
for _ in range(M):
    u,v,a,b=map(int,input().split())
    graph_yen[u].append((a,v))
    graph_yen[v].append((a,u))
    graph_snuke[u].append((b,v))
    graph_snuke[v].append((b,u))
    
yen=dijkstra(S,graph_yen,N)
snuke=dijkstra(T,graph_snuke,N)
minimum_case=[10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i]-=(yen[i+1]+snuke[i+1])
for i in range(N-1,-1,-1):
    minimum_case[i]=max(minimum_case[i],minimum_case[i+1])
for i in range(1,N+1):
    print(minimum_case[i])

Submission status: Accepted

Solution code:
import heapq
N,M,S,T = map(int,input().split())

adj=[[] for _ in range(N)]

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].append((b-1,c,d))
    adj[b-1].append((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,S-1)


while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen<D_S[next_node]:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_S[next_node]*N+next_node)

Q=[]
heapq.heappush(Q,T-1)

while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen<D_T[next_node]:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_T[next_node]*N+next_node)


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


for a in reversed(ans):
    print(10**15-a)

Submission status: Accepted

Solution code:
import heapq
n,m,s,t = map(int,input().split())
edgeY = [[] for _ in range(n)]
edgeS = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgeY[u-1].append((a, v-1))
    edgeY[v-1].append((a, u-1))
    edgeS[u-1].append((b, v-1))
    edgeS[v-1].append((b, u-1))
costY = [float('inf')]*n
costS = [float('inf')]*n
costY[s-1] = 0
costS[t-1] = 0

# 円の時
q = []
for i in edgeY[s-1]:
    heapq.heappush(q, i)
while len(q):
    nowEdge = heapq.heappop(q)
    if costY[nowEdge[1]] == float('inf'):
        costY[nowEdge[1]] = nowEdge[0]
        for i in edgeY[nowEdge[1]]:
            heapq.heappush(q , (i[0]+costY[nowEdge[1]], i[1]))

# スヌークの時
q = []
for i in edgeS[t-1]:
    heapq.heappush(q, i)        
while len(q):
    nowEdge = heapq.heappop(q)
    if costS[nowEdge[1]] == float('inf'):
        costS[nowEdge[1]] = nowEdge[0]
        for i in edgeS[nowEdge[1]]:
            heapq.heappush(q , (i[0]+costS[nowEdge[1]], i[1]))
cost = []
ans = []
first = 10**15
minCost = 10**15
for i in range(n-1,-1,-1):
    nowCost = costY[i]+costS[i]
    if minCost > nowCost:
        minCost = nowCost
    ans.append(minCost)
for i in range(n-1,-1,-1):
    print(first- ans[i])

Submission status: Accepted

Solution code:
import heapq
from sys import stdin
input = stdin.readline
def dijkstra_heap(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())

y_edge = [[] for i in range(n)]
s_edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,yen,strc = map(int,input().split())
    y_edge[x-1].append([yen,y-1])
    y_edge[y-1].append([yen,x-1])
    s_edge[x-1].append([strc,y-1]) 
    s_edge[y-1].append([strc,x-1])

y_dis = dijkstra_heap(s-1,y_edge)
s_dis = dijkstra_heap(t-1,s_edge)
m = 0
ans = []
for y,s in zip(y_dis[::-1], s_dis[::-1]):
    t = 10**15-y-s
    m = max(m,t)
    ans.append(m)

print(*ans[::-1], sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
INF = 10**100

def dijkstra(N, s, i):
  visited = [False]*(N+1)
  costs = [INF]*(N)
  costs[s-1] = 0

  pq = [(0,s)]
  while pq:
    c, n = heapq.heappop(pq)
    visited[n] = True
    for nei,*fee in adj_list[n]:
      if visited[nei]: continue
      if c+fee[i] < costs[nei-1]:
        costs[nei-1] = c+fee[i]
        heapq.heappush(pq, (costs[nei-1],nei))

  return costs

n,m,s,t = map(int, input().split())
adj_list = defaultdict(list)
for _ in range(m):
  u,v,a,b = map(int, input().split())
  adj_list[u].append((v,a,b))
  adj_list[v].append((u,a,b))

yen_costs = dijkstra(n, s, 0)
snk_costs = dijkstra(n, t, 1)
total_costs = list(map(sum, zip(yen_costs, snk_costs)))
comp = INF
res = []
for c in reversed(total_costs):
  if c < comp:
    res.append(int(1e15 - c))
    comp = c
  else:
    res.append(int(1e15 - comp))

print("\n".join(map(str, reversed(res))))

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

INF = 10 ** 16

class edge:
    def __init__(self, to, yen, snuuk):
        self.to = to
        self.cost = [yen, snuuk]

def main():
    mon = 10 ** 15
    N, M, S, T = (int(_) for _ in input().split())
    E = defaultdict(list)
    for _ in range(M):
        u, v, a, b = (int(_) for _ in input().split())
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    def dijkstra(s, y):
        que = list()
        heapq.heapify(que)
        newd = [INF] * (N+1)
        newd[s] = 0
        heapq.heappush(que, [newd[s], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if newd[v] < p[0]: continue
            for e in E[v]:
                if newd[e.to] > newd[v] + e.cost[y]:
                    newd[e.to] = newd[v] + e.cost[y]
                    heapq.heappush(que, [newd[e.to], e.to])
        return newd

    ds = dijkstra(S, 0)
    dt = dijkstra(T, 1)
    output = []
    ret = -1
    for i in range(1, N+1)[::-1]:
        ret = max(ret, mon - (ds[i] + dt[i]))
        output.append(ret)
    print(*output[::-1], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


def dijkstra1(V, n, inf, source):
    # O(ElogV)

    dist = [inf] * (n+1)
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist


def solve():
    n, m, s, t = map(int, input().split())
    V1 = defaultdict(list)
    V2 = defaultdict(list)
    INF = 10**20

    for _ in range(m):
        u, v, a, b = map(int, input().split())
        V1[u].append((a, v))
        V1[v].append((a, u))
        V2[u].append((b, v))
        V2[v].append((b, u))

    d1 = dijkstra1(V1, n, INF, s)
    d2 = dijkstra1(V2, n, INF, t)

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

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


if __name__ == "__main__":
    solve()