143AC - SoundHound (D): Saving Snuuk

SoundHound-D (400 points)

問題

• すぬけ国には 個の都市 と, 都市間をつなぐ 本の電車がある.
• 番目の電車は都市 と を両方向に走っている.
• 番目の電車の運賃は 円 / スヌークである（円とスヌークはすぬけ国の通貨）.
• 両替所では 円を スヌークに両替可能だが, 持っている円を全てスヌークに両替しなければならない. スヌーク→円の両替は不可.
• 現在は全ての都市に両替所が存在するが, 都市 の両替所は 年後に閉鎖.
• 年後に 円を持って都市 から に, どこかで円をスヌークに両替しながら旅行するとき, のそれぞれについて, 都市 到着時点の手持ちスヌークの最大値を求める.

• 
• 
• 
• 
• 
• 
• のとき または
• どの都市からどの都市へも電車を乗り継ぐことで到達可能
• 入力は全て整数

方針

• 両替
• 両替までは円, 両替後はスヌークなので, 辺のコストを としたグラフをそれぞれ構築
• それぞれのグラフ上で からの最短路をダイクストラ法で求める.
• どこの両替所を使うのがベストか決める.
• 両替所の数が多いと面倒なので, 都市 しか使えない状態から考えて, 帰納法っぽく都市を増やしていく.
• 都市 が使える場合に使うべき両替所 = 都市 or 都市 が使える場合に使うべき両替所

import heapq

# dijkstra
# edges = |V|のリスト
# 頂点iから頂点jにコストwで移動可能な場合：edges[i] = [(j, w)]

def dijkstra(n, edges, start):
    INF = float('inf')
    vertices = [INF] * n # 初期化
    vertices[start] = 0 # スタートの距離はゼロ
    hq = [(0, start)]
    heapq.heapify(hq)

    while hq:
        cost, v = heapq.heappop(hq)

        for to, w in edges[v]: # vとの間にedgeが存在する頂点のコストを更新
            if cost + w >= vertices[to]: # 最短距離が更新されない場合
                continue
            vertices[to] = cost + w # 最短距離が更新される場合
            heapq.heappush(hq, (vertices[to], to))

    return vertices

# input
n, m, s, t = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(m)]
INF = float('inf')

# 円とスヌークそれぞれについてグラフを構築
G_yen = [[] for _ in range(n)]
G_snu = [[] for _ in range(n)]

s, t = s - 1, t - 1

for u, v, a, b in G:
    G_yen[u - 1].append((v - 1, a))
    G_yen[v - 1].append((u - 1, a))
    G_snu[u - 1].append((v - 1, b))
    G_snu[v - 1].append((u - 1, b))

# 円/スヌークの場合のs/tからの最短距離
yen = dijkstra(n, G_yen, s)
snu = dijkstra(n, G_snu, t)

ans = [INF]

# 時間を逆から（経由地＝両替所の選択肢が少ない順）
for i in reversed(range(n)):
    tmp = snu[i] + yen[i]
    ans.append(min(ans[-1], tmp))

for i in reversed(ans[1:]):
    print(10 ** 15 - i)