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:
def dijkstra_heap(n,s,edge,k):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n  # True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, [e[k],e[2]])
    while edgelist:
        minedge = 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[2]]:
                heappush(edgelist, [e[k] + d[v], e[2]])
    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(snuke-cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(snuke-cur)
        else:
            ans.append(snuke-cur)
    for v in ans[::-1]:
        print(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()

Submission status: Accepted

Solution code:
def dijkstra_heap(n,s,edge,k):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n  # True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, [e[k],e[2]])
    while edgelist:
        minedge = 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[2]]:
                heappush(edgelist, [e[k] + d[v], e[2]])
    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(snuke-cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(snuke-cur)
        else:
            ans.append(snuke-cur)
    for v in ans[::-1]:
        print(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()

Submission status: Accepted

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

import heapq as hp

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

INF = 10**18

def dijkstra(graph, s):
    D = [INF for _ in range(N)] # 頂点iへの最短距離がD[i]
    D[s] = 0 
    q = [] # しまっていく優先度付きキュー
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
        if D[np] < nd: # 追加した後の残骸は見ない
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
                D[p] = D[np] + d
                hp.heappush(q, (D[p], p))
    
    return D

Ds = dijkstra(graph_y, S-1)
Dg = dijkstra(graph_s, G-1)

ans = [None]*N
ans[N-1] = Ds[N-1] + Dg[N-1]
for n in reversed(range(N-1)):
    ans[n] = min(ans[n+1], Ds[n]+Dg[n])

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
n, m, s, t = map(int, input().split())
e = dd(list)
money = 10 ** 15
for _ in range(m):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  e[u + n].append((v + n, b))
  e[v + n].append((u + n, b))
"""
for i in range(1, n + 1):
  e[i].append((i + n, 0))
"""
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 15)
      v0 = v // (10 ** 15)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 15) + p[0])
    return d
d = dijkstra(2 * n + 1, e)
x = d.path(s, 2 * n + 1)
y = d.path(t + n, 2 * n + 1)
#print(x)
#print(y)
paths = [float("inf")] * (n + 1)
minpaths = [float("inf")] * (n + 1)
for i in range(1, n + 1):
  paths[i] = x[i] + y[n + i]
#print(paths)
minpaths[-1] = paths[-1]
for i in range(n - 1, -1, -1):
  minpaths[i] = min(minpaths[i + 1], paths[i])
#print(minpaths)
for i in range(1, n + 1):
  print(money - minpaths[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
# mod = 10**9 + 7

class dijkstra:
    def __init__(self, to, start):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        # self.cnt = [0] * self.N
        # self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                # if self.dist[nv] == self.dist[v] + w:
                #     self.cnt[nv] += self.cnt[v]
                #     self.cnt[nv] %= mod

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

JPY = dijkstra(jpy, s)
JPY.update()
SNUKE = dijkstra(snuke, t)
SNUKE.update()

cost_list = []
cost = inf

for i in range(n)[::-1]:
    cost = min(cost, JPY.dist[i] + SNUKE.dist[i])
    cost_list.append(cost)

cost_list.reverse()
for cost in cost_list:
    ans = pow(10, 15) - cost
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7

class dijkstra:
    def __init__(self, to, start):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.cnt = [0] * self.N
        self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                if self.dist[nv] == self.dist[v] + w:
                    self.cnt[nv] += self.cnt[v]
                    self.cnt[nv] %= mod

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

JPY = dijkstra(jpy, s)
JPY.update()
SNUKE = dijkstra(snuke, t)
SNUKE.update()

cost_list = []
cost = inf

for i in range(n)[::-1]:
    cost = min(cost, JPY.dist[i] + SNUKE.dist[i])
    cost_list.append(cost)

cost_list.reverse()
for cost in cost_list:
    ans = pow(10, 15) - cost
    print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse.csgraph import dijkstra

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	def dijkstra(E, start):
	    N_d = len(E)
	    dist = [INF] * N_d
	    dist[start] = 0
	    q = [(0, start)]
	    while q:
	        dist_v, v = heappop(q)
	        if dist[v] != dist_v:
	            continue
	        for u, dist_vu in E[v]:
	            dist_u = dist_v + dist_vu
	            if dist_u < dist[u]:
	                dist[u] = dist_u
	                heappush(q, (dist_u, u))
	    return dist

	n, m, s, t = MAP()

	uvab = [LIST() for _ in range(m)]

	A = [[] for _ in range(n+1)]
	B = [[] for _ in range(n+1)]

	for u, v, a, b in uvab:
		A[u].append((v, a))
		A[v].append((u, a))
		B[u].append((v, b))
		B[v].append((u, b))

	distA = dijkstra(A, s)  # 円での移動(s->i)
	distB = dijkstra(B, t)  # スヌークでの移動(t->i)

	Ans = []
	init = 10**15
	ans = INF
	for a, b in zip(distA[:0:-1], distB[:0:-1]):
		ans = min(ans, a+b)
		Ans.append(init-ans)
	Ans = Ans[::-1]
	print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse.csgraph import dijkstra

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

n, m, s, t = MAP()

uvab = [LIST() for _ in range(m)]

A = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for u, v, a, b in uvab:
	A[u].append((v, a))
	A[v].append((u, a))
	B[u].append((v, b))
	B[v].append((u, b))

distA = dijkstra(A, s)  # 円での移動(s->i)
distB = dijkstra(B, t)  # スヌークでの移動(t->i)

Ans = []
init = 10**15
ans = INF
for a, b in zip(distA[:0:-1], distB[:0:-1]):
	ans = min(ans, a+b)
	Ans.append(init-ans)
Ans = Ans[::-1]
print("\n".join(map(str, Ans)))

Submission status: Accepted

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  #q = [(startからの距離, 現在地)]
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance


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

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = info[i]
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

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

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

Submission status: Accepted

Solution code:

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

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

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

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

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

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())



en=Graph()
snu=Graph()

for i in range(m):
    u,v,a,b=map(int,input().split())
    en.add_edge(u,v,a)
    en.add_edge(v,u,a)
    snu.add_edge(u,v,b)
    snu.add_edge(v,u,b)

enen=Dijkstra(en,s)
snusnu=Dijkstra(snu,t)
ans=[enen.shortest_distance(n)+snusnu.shortest_distance(n)]

for i in range(n-1,0,-1):
    d1=enen.shortest_distance(i)
    d2=snusnu.shortest_distance(i)
    ans.append(min(ans[-1],d1+d2))


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

Submission status: Accepted

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        if distances[fr] != dist:
            continue

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if distances[to] > new_dist:
                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

    return distances


from_start_yen = dijkstra(G_yen, S)
from_goal_snuuk = dijkstra(G_snuuk, T)

ans = [0] * (N + 1)
for i, yen, snuuk in zip(reversed(range(N)), from_start_yen[::-1], from_goal_snuuk[::-1]):
    ans[i] = max(ans[i + 1], 10 ** 15 - (yen + snuuk))

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

Submission status: Accepted

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    fixed = [False] * n
    distances[start] = 0

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        fixed[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (fixed[to] is False) and (distances[to] > new_dist):
                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

    return distances


from_start_yen = dijkstra(G_yen, S)
from_goal_snuuk = dijkstra(G_snuuk, T)

ans = [0] * (N + 1)
for i, yen, snuuk in zip(reversed(range(N)), from_start_yen[::-1], from_goal_snuuk[::-1]):
    ans[i] = max(ans[i + 1], 10 ** 15 - (yen + snuuk))

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

Submission status: Accepted

Solution code:
import sys

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

    def dijkstra(E, start):
        from heapq import heappush, heappop
        N = len(E)
        inf = float("inf")
        dist = [inf] * N
        dist[start] = 0
        q = [(0, start)]
        while q:
            dist_v, v = heappop(q)
            if dist[v] != dist_v:
                continue
            for u, dist_vu in E[v]:
                dist_u = dist_v + dist_vu
                if dist_u < dist[u]:
                    dist[u] = dist_u
                    heappush(q, (dist_u, u))
        return dist

    dist_A = dijkstra(A, S)
    dist_B = dijkstra(B, T)
    init = 10**15
    Ans = []
    ans = float("inf")
    for a, b in zip(dist_A[:0:-1], dist_B[:0:-1]):
        ans = min(ans, a+b)
        Ans.append(init-ans)
    Ans.reverse()
    print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())

en=[[]for i in range(n+1)]
sn=[[]for i in range(n+1)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    en[v].append((u,a))
    en[u].append((v,a))
    sn[v].append((u,b))
    sn[u].append((v,b))
#print(en)

import numpy as np
INF=10**20

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    shortest=[INF]*N
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        for dst, d1 in paths[src]:
            if d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
    return np.array(shortest)
    
en=dijkstra(s,n+1,en)
sn=dijkstra(t,n+1,sn)

cost=[]
for i in range(1,n+1):
    cost.append(en[i]+sn[i])
cost=cost[::-1]
#print(cost)

ans=[]
mi=cost[0]
for i in range(n):
    ans.append(min(mi,cost[i]))
    mi=min(mi,cost[i])
ans=ans[::-1]
#print(ans)
for i in ans:
    print(10**15-i)

Submission status: Accepted

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

en=[[]for i in range(n+1)]
sn=[[]for i in range(n+1)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    en[v].append((u,a))
    en[u].append((v,a))
    sn[v].append((u,b))
    sn[u].append((v,b))
#print(en)

import numpy as np
INF=10**20

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    shortest=[INF]*N
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        for dst, d1 in paths[src]:
            if d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
    return np.array(shortest)
    
en=dijkstra(s,n+1,en)
sn=dijkstra(t,n+1,sn)

cost=[]
for i in range(1,n+1):
    cost.append(en[i]+sn[i])
cost=cost[::-1]
#print(cost)

ans=[]
mi=cost[0]
for i in range(n):
    ans.append(min(mi,cost[i]))
    mi=min(mi,cost[i])
ans=ans[::-1]
#print(ans)
for i in ans:
    print(10**15-i)

Submission status: Accepted

Solution code:
import heapq
inf = float('inf')
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist

n, m, s, t = map(int, input().split())
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    G1[u-1].append((a, v-1))
    G1[v-1].append((a, u-1))
    G2[u-1].append((b, v-1))
    G2[v-1].append((b, u-1))
dist1 = dijkstra(s-1, n, G1)
dist2 = dijkstra(t-1, n, G2)
ans = [0]*n
ans[-1] = dist1[n-1]+dist2[n-1]
for i in range(n-1)[::-1]:
    ans[i] = min(ans[i+1], dist1[i]+dist2[i])
for i in range(n):
    print(10**15-ans[i])

Submission status: Accepted

Solution code:
import heapq,collections
class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d):
        self.e[u].append((v,d))
        self.e[v].append((u,d))
    def search(self,s):
        dist = [-1 for _ in range(n)]
        next_point = []
        heapq.heappush(next_point,(0,s))
        while next_point:
            cost,node = heapq.heappop(next_point)
            if dist[node] == -1:
                dist[node] = cost
                for u,d in self.e[node]:
                    if dist[u] == -1:
                        heapq.heappush(next_point,(cost+d,u))
        return dist

n,m,s,t = map(int,input().split())
graph_y = Dijkstra()
graph_s = Dijkstra()
for _ in range(m):
    u,v,a,b = map(int,input().split())
    graph_y.add(u-1,v-1,a)
    graph_s.add(u-1,v-1,b)
dist_y = graph_y.search(s-1)
dist_s = graph_s.search(t-1)
r = [0]*n
for i in range(n):
    r[-i-1] = max(r[-i],10**15-dist_y[-i-1]-dist_s[-i-1])
print(*r,sep='\n')

Submission status: Accepted

Solution code:
n,m,s,t = map(int,input().split())
import collections
edge = collections.defaultdict(list)
for _ in range(m):
    u,v,a,b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])
yen_dist = [-1 for _ in range(n)]
sunuk_dist = [-1 for _ in range(n)]

import heapq
next_point = []
heapq.heappush(next_point,(0,s-1))
while next_point:
    cost,node = heapq.heappop(next_point)
    if yen_dist[node] == -1:
        yen_dist[node] = cost
        for u,a,_ in edge[node]:
            if yen_dist[u] == -1:
                heapq.heappush(next_point,(cost+a,u))

heapq.heappush(next_point,(0,t-1))
while next_point:
    cost,node = heapq.heappop(next_point)
    if sunuk_dist[node] == -1:
        sunuk_dist[node] = cost
        for u,_,b in edge[node]:
            if sunuk_dist[u] == -1:
                heapq.heappush(next_point,(cost+b,u))

r = [0]*n
for i in range(n):
    r[-i-1] = max(r[-i],10**15-yen_dist[-i-1]-sunuk_dist[-i-1])
print(*r,sep='\n')

Submission status: Accepted

Solution code:
#ダイクストラ法(単一始点最短路)　計算量O(|E|log|V|)
#V:頂点の集合 E:辺の集合
#負の辺が含まれるときはベルマンフォード法
import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d,directed=False):
        #0-indexedでなくても良いことに注意
        #u=from,v=to,d=cost
        #directed =Trueなら、有向グラフ
        if directed is False:
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:
            self.e[u].append([v,d])
    def delete(self,u,v):
        self.e[u]=[_ for _ in self.e[u] if _[0]!=v]
        self.e[v]=[_ for _ in self.e[v] if _[0]!=u]
    def search(self,s):
        #:param s:始点
        #:return: 始点から各点までの最短経路
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
        return d

#Saving Shuuk
n,m,s,t=map(int,input().split())
uvab=l=[list(map(int, input().split())) for i in range(m)]
#print(l)
graph1=Dijkstra()
graph2=Dijkstra()
for u,v,a,b in l:
    graph1.add(u,v,a)
    graph2.add(u,v,b)

result_a=graph1.search(s) #{2: 0, 1: 1, 4: 2, 3: 21})
result_b=graph2.search(t) #{3: 0, 1: 1, 4: 101, 2: 11})
ans_list=[float('inf')]   #[inf]

for i in range(n,0,-1):
    cur=result_a[i]+result_b[i]
    if cur>ans_list[-1]:
        cur=ans_list[-1]
    ans_list.append(cur)
#ans_list #[inf, 103, 21, 11, 2]

for i in range(len(ans_list[1:])):
    print(10**15-ans_list[-(i+1)])

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
uvab=[map(int,input().split()) for i in range(m)]
inf=10**20
c1=[[] for i in range(n)]
c2=[[] for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1].append((v-1,a))
    c1[v-1].append((u-1,a))
    c2[u-1].append((v-1,b))
    c2[v-1].append((u-1,b))
from heapq import heappop,heappush
def dij(c,N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v,w in c[u]:
            if w<inf:
                temp=d[u]+w
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d1=dij(c1,n,s-1)
d2=dij(c2,n,t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')

Submission status: Accepted

Solution code:
import heapq

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

cost = [[] for _ in range(n)]
for i in range(m):
    cost[L[i][0]-1].append((L[i][2], L[i][3], L[i][1]-1))
    cost[L[i][1]-1].append((L[i][2], L[i][3], L[i][0]-1))
    
def dijkstra(s, n, cost, c):
    g = 10**6
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    used[s] = 1
    edgelist = []
    for e in cost[s]:
        heapq.heappush(edgelist, e[c]*g+e[2])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%g] == 1:
            continue
        v = minedge%g
        d[v] = minedge//g
        used[v] = 1
        for e in cost[v]:
            if used[e[2]] == 0:
                heapq.heappush(edgelist, (e[c]+d[v])*g + e[2])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snuuk = dijkstra(t-1, n, cost, 1)
ans_list = [0]*n
ans_list[n-1] = jpy[n-1]+snuuk[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snuuk[i])
    
for i in range(n):
    print(10**15-ans_list[i])