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 heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
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

n,m,s,t = map(int, input().split())
graph = [[] for i in range(n+1)]
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])
money = dijkstra(s,0)
snu = dijkstra(t,1)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))

Submission status: Accepted

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

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d1[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g1[v])): #頂点vの隣接リストを走査
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: #距離が更新できるかを検討
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d1)

d2[t] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, t]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d2[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g2[v])): #頂点vの隣接リストを走査
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: #距離が更新できるかを検討
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d2)

tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

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

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())
edge1=[[] for i in range(n)]
edge2=[[] for i in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    edge1[u-1].append(a*(10**6)+(v-1))
    edge1[v-1].append(a*(10**6)+(u-1))
    edge2[u-1].append(b*(10**6)+(v-1))
    edge2[v-1].append(b*(10**6)+(u-1)) 

def dijkstra_heap(edge,s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d

d1=dijkstra_heap(edge1,s-1)
d2=dijkstra_heap(edge2,t-1)
d=[0]*n

for i in range(n):
  d[i]=d1[i]+d2[i]
for i in range(n-1):
  d[-i-2]=min(d[-i-2],d[-i-1])
for dd in d:
  print(10**15-dd)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


N, M, S, T = map(int, input().split())
PATH = [[] for _ in range(N+1)]


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


def dijkstra(s, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[s] = 0
    que = [(0, s)]

    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue

        for u, *a in PATH[v]:
            dv = d + a[mode]

            if dv < dist[u]:
                dist[u] = dv
                heappush(que, (dv, u))

    return dist


da = dijkstra(S, 0)
db = dijkstra(T, 1)

score = [10**15 - (da[i]+db[i]) for i in range(1, N+1)]

ans = [10**15] * N
ans[-1] = score[-1]

for i in range(N-2, -1, -1):
    ans[i] = max(ans[i+1], score[i])

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

Submission status: Accepted

Solution code:
#import sys
from heapq import heappop, heappush
import numpy as np

#stdin = sys.stdin


N, M, S, T = list(map(int, input().split()))
graph = [[] for _ in range(N+1)] #0使わず
for _ in range(M):
    u, v, a, b = list(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) #0使わず
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))
# 21

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M, S, T = list(map(int, input().split()))
graph = [[] for _ in range(N+1)] #0使わず
for _ in range(M):
    u, v, a, b = list(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) #0使わず
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))
# 21

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M, S, T = rl()
graph = [[] for _ in range(N+1)] #0使わず
for _ in range(M):
    u, v, a, b = rl()
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    # 各地点への最小コストを返す
    INF = 10 ** 15
    dist = [INF] * (N+1) #0使わず
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))
# 21

Submission status: Accepted

Solution code:
from heapq import*
def D(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]:
   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);A,m=[],0
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),
for y,s in zip(D(s-1,e)[::-1],D(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 D(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]:
   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(D(s-1,e)[::-1],D(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(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]:
   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(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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

def Dijkstra(num, start, vedge):
    """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
    """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
    """ dist[i] は start から i までの最短距離 """

    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in vedge[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist



#solve
def solve():
    n, m, s, t = LI()
    s -= 1
    t -= 1
    uva = defaultdict(list)
    uvb = defaultdict(list)
    for _ in range(m):
        u, v, a, b = LI_()
        a += 1
        b += 1
        uva[u].append((v, a))
        uva[v].append((u, a))
        uvb[u].append((v, b))
        uvb[v].append((u, b))
    dista = Dijkstra(n, s, uva)
    distb = Dijkstra(n, t, uvb)
    a = [None] * n
    for i in range(n):
        a[i] = dista[i] + distb[i]
    a = a[::-1]
    for i in range(1,n):
        a[i] = min(a[i], a[i - 1])
    a = a[::-1]
    for i in range(n):
        print(10**15-a[i])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq

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

dic = {}

for i in range(m):

    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,a,b])
    dic[v].append([u,a,b])



q = [[0,t]]

yen = [float("inf")] * n
yen[t] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[2]:
            yen[vab[0]] = yen[du[1]] + vab[2]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])

sunk = yen.copy()


q = [[0,s]]

yen = [float("inf")] * n
yen[s] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[1]:
            yen[vab[0]] = yen[du[1]] + vab[1]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])


cost = []

for i in range(n):
    cost.append( yen[i] + sunk[i] )

costq = []

for i in range(n):
    heapq.heappush(costq , [cost[i] , i])

for i in range(n):

    while costq[0][1] < i:
        heapq.heappop(costq)

    print (10 ** 15 - costq[0][0])

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


N, M, s, t = map(int, input().split())  # N個の町, M本の電車, 始点s, 終点t
s -= 1
t -= 1
# 最後は終点でしかスヌークにしか変えられなくなる
graph = Graph()
reverse_graph = Graph()
for _ in range(M):
    u, v, a, b = map(int, input().split())  # 始点, 終点, 円, スヌーク
    u -= 1
    v -= 1
    graph.add_edge(u, v, a)
    graph.add_edge(v, u, a)
    reverse_graph.add_edge(u, v, b)
    reverse_graph.add_edge(v, u, b)


shortest_from_start = Dijkstra(graph, s)
shortest_from_goal = Dijkstra(reverse_graph, t)


# 逆から考える, どんどん選択肢が増えるようにする, 最初は一番厳しい制約
price = shortest_from_start.shortest_distance(N-1)+shortest_from_goal.shortest_distance(N-1)
ans = [price]  # 最後にreverseする

# 最初に、どこでも換金できないパターンの値を求めて、それから、換金できる場所を増やしていってそこで換金する場合に値が変わるかどうかを確かめていく
for i in reversed(range(N-1)):  # iが換金する場所
    ans.append(min(ans[-1], shortest_from_start.shortest_distance(i)+shortest_from_goal.shortest_distance(i)))
ans.reverse()

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    v2 = [[] for i in range(n)]
    for i in range(m):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
        v2[a].append((b,d))
        v2[b].append((a,d))
    d = [float("inf")]*n
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            nd = dx+c
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    d2 = [float("inf")]*n
    d2[t] = 0
    q = [(0,t)]
    while q:
        dx,x = heappop(q)
        for y,c in v2[x]:
            nd = dx+c
            if nd < d2[y]:
                d2[y] = nd
                heappush(q,(nd,y))
    ans = [10**15-(d[i]+d2[i]) for i in range(n)]
    for i in range(n-1)[::-1]:
        if ans[i+1] > ans[i]:
            ans[i] = ans[i+1]
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, a, b]) for u, v, a, b in uvab]
    [g[v-1].append([u-1, a, b]) for u, v, a, b in uvab]

    import heapq

    yen = np.full(n, np.inf)
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == np.inf:
            yen[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+y, x))

    snk = np.full(n, np.inf)
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == np.inf:
            snk[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+z, x))

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

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

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

    import heapq

    inf = 10**15

    yen = [inf for _ in [0]*n]
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == inf:
            yen[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+y, x))

    snk = [inf for _ in [0]*n]
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == inf:
            snk[i] = d
            for x, y, z in g[i]:
                heapq.heappush(h, (d+z, x))

    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)


main()

Submission status: Accepted

Solution code:
from itertools import accumulate


def dijkstra(n, s, adj_list):
    # 始点sから各頂点への最短距離
    # n: 頂点数
    from heapq import heappush, heappop

    dists = [float('inf')] * n
    dists[s] = 0
    heap, rem = [(0, s)], n - 1

    while heap and rem:
        cost, src = heappop(heap)
        if dists[src] < cost:
            continue
        rem -= 1

        for dest, _cost in adj_list[src]:
            newcost = cost + _cost
            if dists[dest] > newcost:
                dists[dest] = newcost
                heappush(heap, (newcost, dest))

    return dists


N, M, S, T = map(int, input().split())
S -= 1
T -= 1
adj_yen = [[] for _ in range(N)]
adj_snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    adj_yen[u].append((v, a))
    adj_yen[v].append((u, a))
    adj_snuuk[u].append((v, b))
    adj_snuuk[v].append((u, b))
yen_cost = dijkstra(N, S, adj_yen)
snuuk_cost = dijkstra(N, T, adj_snuuk)
ans = list(accumulate([10**15-yen-snuuk for yen, snuuk in zip(yen_cost, snuuk_cost)][::-1], max))[::-1]
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import heapq

# s:始点, path[from]:[[cost,to]...] 隣接リスト
def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d


n,m,s,t = map(int, input().split())
s-=1
t-=1
train = [list(map(int, input().split())) for i in range(m)]

yen = [[] for i in range(n)]
snuke = [[] for i in range(n)]

for i in range(m):
    u,v,a,b = train[i]
    u-=1
    v-=1
    yen[u].append([a,v])
    yen[v].append([a,u])
    snuke[u].append([b,v])
    snuke[v].append([b,u])

from_s = dijkstra(s,yen)
to_t = dijkstra(t,snuke)

left = [0 for i in range(n)]
left[-1]=from_s[n-1]+to_t[n-1]


for i in range(1,n):
    left[-i-1]=min(left[-i],from_s[-i-1]+to_t[-i-1])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def resolve():
    n,m,s,t=map(int,input().split())
    s-=1; t-=1
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,a))
        E[v].append((u,a))
        R[u].append((v,b))
        R[v].append((u,b))

    # Dijkstra with heapq
    dist1=[INF]*n
    dist1[s]=0
    Q=[(0,s)]
    while(Q):
        d,v=heappop(Q)
        if(dist1[v]<d): continue
        for nv,w in E[v]:
            if(dist1[nv]>dist1[v]+w):
                dist1[nv]=dist1[v]+w
                heappush(Q,(dist1[nv],nv))

    dist2=[INF]*n
    dist2[t]=0
    Q=[(0,t)]
    while(Q):
        d,v=heappop(Q)
        if(dist2[v]<d): continue
        for nv,w in R[v]:
            if(dist2[nv]>dist2[v]+w):
                dist2[nv]=dist2[v]+w
                heappush(Q,(dist2[nv],nv))

    # s -> v -> t の最短を計測する
    dist=[dist1[v]+dist2[v] for v in range(n)]
    # 後ろから min をとる
    for i in range(n-1,0,-1):
        dist[i-1]=min(dist[i-1],dist[i])

    M=10**15
    for v in range(n):
        print(M-dist[v])
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
G1 = defaultdict(list); G2 = defaultdict(list)
N, M, S, T = map(int, input().split())
S-=1; T-=1
for i in range(M):
    f, t , v1, v2 = map(int, input().split())
    G1[f-1].append((t-1, v1))
    G1[t-1].append((f-1, v1))
    G2[f-1].append((t-1, v2))
    G2[t-1].append((f-1, v2))

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**16
d1 = [INF]*N; d2 = [INF]*N

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # print(f'd[{v}] = {cost}')
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

dijkstra(S, G1, d1)
dijkstra(T, G2, d2)
"""
for i in range(N):
    ans = 0
    for j in range(i, N):
        ans = max(ans, 10**15-d1[j]-d2[j])
    print(ans)
"""
anses = [0]*N
ans = 10**15
for i in range(N):
    ans = min(ans, d1[N-1-i]+d2[N-1-i])
    anses[N-1-i]=10**15-ans
for i in range(N):
    print(anses[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

uv = [[] for _ in range(n)]
for _ in range(m) :
    u, v, a, b = map(int, input().split())
    uv[u-1].append((v-1, a, b))
    uv[v-1].append((u-1, a, b))
    
q = [(0, s-1)]
ca = [float('inf')] * n
ca[s-1] = 0
while q :
    cco, cur = heappop(q)
    if cco > ca[cur] :
        continue
    for nex, nco, _ in uv[cur] :
        if cco + nco < ca[nex] :
            ca[nex] = cco + nco
            heappush(q, (cco + nco, nex))
            
q = [(0, t-1)]
cb = [float('inf')] * n
cb[t-1] = 0
while q :
    cco, cur = heappop(q)
    if cco > cb[cur] :
        continue
    for nex, _, nco in uv[cur] :
        if cco + nco < cb[nex] :
            cb[nex] = cco + nco
            heappush(q, (cco + nco, nex))

m = [(ca[i] + cb[i], i) for i in range(n)]
m.sort(reverse=True)

for i in range(n) :
    print(10 ** 15 - m[-1][0])
    while m and m[-1][1] <= i :
        m.pop()

Submission status: Accepted

Solution code:
def dijkstra_heap(n,s,edge,k):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    d[s] = 0
    edgelist = [s]
    while edgelist:
        nextedge = []
        for i in edgelist:
            for j in edge[i]:
                next = j[2]
                c = j[k]
                if d[next] > c + d[i]:
                    d[next] = c + d[i]
                    nextedge.append(next)
        edgelist = nextedge
    return d

def examD():
    N, M, s, t = LI()
    edge = defaultdict(list)
#    edge2 = defaultdict(list)
    # edge2 メモリ無駄
    for i in range(M):
        x, y, z1, z2 = map(int, input().split())
        x -=1; y -=1
        edge[x].append((z1,z2,y))
        edge[y].append((z1,z2,x))
    start1 = s-1
    start2 = t-1
    res1 = dijkstra_heap(N,start1, edge,0)
    res2 = dijkstra_heap(N,start2, edge,1)
    ans = []
    snuke = 10**15
    cur = res1[N-1] + res2[N-1]
    ans.append(cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(cur)
        else:
            ans.append(cur)
    for v in ans[::-1]:
        print(snuke-v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()