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:
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    q = [(0, start)] # q = [(startからの距離, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            if dist[v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[v] + cost
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist


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

graph_y = [[] for i in range(n)]
graph_s = [[] for i in range(n)]
for u, v, a, b in info:
    u -= 1
    v -= 1
    graph_y[u].append((v, a))
    graph_y[v].append((u, a))
    graph_s[u].append((v, b))
    graph_s[v].append((u, b))
    
s -= 1
t -= 1
dist_y = dijkstra(s, graph_y)
dist_s = dijkstra(t, graph_s)

ans = 10 ** 18
ret = [10 ** 15] * n
for i in range(n)[::-1]:
    tmp = dist_y[i] + dist_s[i]
    ans = min(ans, tmp)
    ret[i] -= ans
for i in ret:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

n,m,s,t = map(int,input().split())#順に都市の数、電車の数、スタート、ゴール
adj_list = [[]for i in range(0,(n+1),1,)]#隣接リスト(都市1~nをそのまま使いたいのでn+1の大きさで宣言して0は使わない)
for i in range(0,m,1):
    u,v,a,b = map(int,input().split())
    adj_list[u].append([v,a,b])#[0]行先[1]円[2]スヌーク
    adj_list[v].append([u,a,b])

D_INF = 10**15
d = [D_INF]*(n+1)#最速到達距離。でかい数で初期化
d[s] = 0#スタート
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:#とりあえず円で
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


d_sn = [D_INF]*(n+1)#最速到達距離。でかい数で初期化
d_sn[t] = 0#スタート
heappush(que,(d_sn[t],t))

while(len(que)):
    time,place = heappop(que)
    if time > d_sn[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d_sn[adj_list[place][i][0]] > time + adj_list[place][i][2]:
             d_sn[adj_list[place][i][0]] = time + adj_list[place][i][2]
             heappush(que,(d_sn[adj_list[place][i][0]],adj_list[place][i][0]))

for i in range(1,n+1,1):
    d[i]=d[i]+d_sn[i]
    heappush(que,(d[i],i))
minimum,minimum_place = heappop(que)

for i in range(0,n,1):
    if minimum_place <= i:
        while(len(que)):
            minimum,minimum_place = heappop(que)
            if minimum_place > i:
                break
    print(10**15-minimum)

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

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

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

n,m,s,t=map(int,input().split())
yen=Dijkstra(n)
snuke=Dijkstra(n)
for i in range(0,m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    yen.add(u,v,a)
    yen.add(v,u,a)
    snuke.add(u,v,b)
    snuke.add(v,u,b)

s-=1
t-=1
answer=[]
ye=yen.shortest_path(s)
sn=snuke.shortest_path(t)
cost=float("inf")
for i in range(n-1,-1,-1):
    cost=min(cost,sn[i]+ye[i])
    answer.append(cost)

for i in range(0,len(answer)):
    print(10**15-answer[-i-1])

Submission status: Accepted

Solution code:
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
edges1 = [[] for i in range(n)]
edges2 = [[] for i in range(n)]
#  1 real world
#  2 snuuk world
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    # real
    edges1[u].append((v,a))
    edges1[v].append((u,a))
    # snuuk
    edges2[u].append((v,b))
    edges2[v].append((u,b))

def dijkstra(N,edges,s):
    q = []
    heapq.heapify(q)
    INF = 10**20

    from datetime import datetime as dt
    x = dt.now()
    cost = [INF] * N
    heapq.heappush(q,(0,s))
    while len(q) > 0:
        c_v,v = heapq.heappop(q)
        # すでに確定しているものは何もしない
        if cost[v] != INF: continue
        # 確定していなければ、最小を更新しつつ、
        # そのnodeから到達する辺とコストをheapqにpush
        else: cost[v] = c_v
        for u,c_u in edges[v]:
            if cost[u] != INF:continue
            c_upd = c_v + c_u
            heapq.heappush(q,(c_upd,u))
    # print(cost)
    return cost


cnt1 = dijkstra(n,edges1,s)
cnt2 = dijkstra(n,edges2,t)
zs = [c1+c2 for c1,c2 in zip(cnt1,cnt2)]
mn = 10**20
ans = []
for z in zs[::-1]:
    mn = min(mn,z)
    ans.append(10**15-mn)

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

Submission status: Accepted

Solution code:
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
edges1 = [[] for i in range(n)]
edges2 = [[] for i in range(n)]
#  1 real world
#  2 snuuk world
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    # real
    edges1[u].append((v,a))
    edges1[v].append((u,a))
    # snuuk
    edges2[u].append((v,b))
    edges2[v].append((u,b))

def dijkstra(n, edges, s):
    INF = 10**20
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    # 初期のやつ
    for v, c in edges[s]:
        # print("v{},c{}".format(v,c))
        # コストを前にしてpushしておく(そこから最小値を取り出すので)
        heapq.heappush(edgelist, (c, v))
    # 空になるまで
    while len(edgelist):
        # コスト最小値を取り出す
        c_min, v_min = heapq.heappop(edgelist)
        # そのエッジがすでに確定していたら終わり
        if used[v_min]:
            continue
        # 確定していなければ、そこから派生するエッジをコスト付与して与える
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d


cnt1 = dijkstra(n,edges1,s)
cnt2 = dijkstra(n,edges2,t)
# print(cnt1)
# print(cnt2)
zs = [c1+c2 for c1,c2 in zip(cnt1,cnt2)]
mn = 10**20
ans = []
for z in zs[::-1]:
    # print(mn,z)
    mn = min(mn,z)
    ans.append(10**15-mn)

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

Submission status: Accepted

Solution code:
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist
import sys
input = sys.stdin.readline
def main():
    n, m, s, t = map(int, input().split())
    s, t = s-1, t-1
    G_y = [[] for _ in range(n)]
    G_s = [[] for _ in range(n)]
    f = [True]*n
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G_y[u].append([v, a])
        G_y[v].append([u, a])
        G_s[u].append([v, b])
        G_s[v].append([u, b])
    cost_y = dijkstra(G_y, s)
    cost_s = dijkstra(G_s, t)
    cost = [[cost_y[i] + cost_s[i], i] for i in range(n)]
    cost.sort()
    x = 0
    for i in range(n):
        while not f[cost[x][1]]:
            x += 1
        print(10**15 - cost[x][0])
        f[i] = False

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Dijkstra修正したので、確認のため使用した。

# ダイクストラ法：単一始点最短路。各距離は非負。
# 時間計算量はO(ElogV)
# s:始点, path[from]:[(to,cost)...] 隣接リスト
# 後述の改善前に比べ、heapqの中身をtupleにしたら速度が改善した
import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    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 to,cost 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

snuke_path = [[] for i in range(n)]
yen_path = [[] for i in range(n)]

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

yen_from_s = dijkstra(s,yen_path)
snuke_to_t = dijkstra(t,snuke_path)

total = [yen_from_s[i]+snuke_to_t[i] for i in range(n)]
ans = [0]*n
ans [-1] = total[-1]
for i in range(n-1):
    ans[-2-i] = min(ans[-1-i],total[-2-i])
ans = [10**15-ans[i] for i in range(n)]

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edage = namedtuple('Edge', 'to cost')

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

s, t = s - 1, t - 1

# 円とスヌークそれぞれグラフを構成する
Yen = [[] for _ in range(n)]
Snuuk = [[] for _ in range(n)]

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

  
def min_costs(graph, start):
  costs = [INF] * n
  costs[start] = 0
  
  q = [P(0, start)]
  
  while q:
    cost, v = heappop(q)
    if cost > costs[v]:
      continue
    for to, cost in graph[v]:
      if costs[to] > costs[v] + cost:
        costs[to] = costs[v] + cost
        heappush(q, P(costs[to], to))        
        
  return costs

min_costs_in_yen = min_costs(Yen, s)
min_costs_in_snuuk = min_costs(Snuuk, t)

total_costs = [
  min_costs_in_yen[i] + min_costs_in_snuuk[i] 
  for i in range(n)
]

# 両替所が閉鎖されていく
for i in range(n - 1, 0, -1):
  total_costs[i - 1] = min(total_costs[i - 1], total_costs[i])
                      
    
for i in range(n):
  print(10 ** 15 - total_costs[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


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

d_yen = dijkstra(g_yen, n, s)
d_snu = dijkstra(g_snu, n, t)

d = [d_yen[i] + d_snu[i] for i in range(n)]

ans = [10**15] * n
ans[n - 1] = d[n - 1]
for i in reversed(range(n - 1)):
    ans[i] = min(ans[i + 1], d[i])

for i in range(n):
    ans[i] = 10**15 - ans[i]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * 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

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(n, s, g, mode):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for w, *a in g[v]:
            nd = d + a[mode]
            if dist[w] > nd:
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    s_dist = dijkstra(n, s, graph, 0)
    t_dist = dijkstra(n, t, graph, 1)

    cost = float("inf")
    ans = [0] * n
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# import heapq
# def dijkstra_heap(n,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

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# 高速化版
import heapq
def dijkstra_heap(n,s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

yen = 10**15
ans = -1*float("inf")
ls_ans = [0]*n
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    ls_ans[i] = ans

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

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# import heapq
# def dijkstra_heap(n,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

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# 高速化版 
import heapq
def dijkstra_heap(n,s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

yen = 10**15
ans = -1*float("inf")
ls_ans = [0]*n
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    ls_ans[i] = ans

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = float("inf")


def Dijkstra(n, s, g, mode):  # (頂点数，始点，グラフ，モード)を引数に
    dist = [INF] * n  # distを初期化
    dist[s] = 0  # 始点の距離は0
    hq = [(0, s)]  # (距離，頂点)で管理
    while hq:  # BFSと同様に探索
        d, v = heappop(hq)  # 最小距離とその頂点を取得
        if dist[v] < d:  # すでに最小になっている時はcontinue
            continue
        for w, *a in g[v]:  # そうでない時は隣接点への重みとその頂点を順に取得
            nd = d + a[mode]
            if dist[w] > nd:  # 最小になっていな開ければ更新してhqにpush
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist


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

    d_yen = Dijkstra(n, s, g, 0)
    d_sunnk = Dijkstra(n, t, g, 1)

    ans = [0] * n
    cost = float("inf")
    for i in range(n-1, -1, -1):
        cost = min(cost, d_yen[i] + d_sunnk[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s, G):
    inf = 1145141919810893
    dist = [inf] * n
    dist[s] = 0
    c = [0] * n
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

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

Submission status: Accepted

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

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return dict(self.__costs)


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [INF] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in costs:
        print(YEN - cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return self.__costs


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [INF] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in costs:
        print(YEN - cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return self.__costs


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [0] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in map(lambda x: YEN - x, costs):
        print(cost)


if __name__ == "__main__":
    main()