結果

問題 No.807 umg tours
ユーザー i_taku
提出日時 2024-06-07 10:48:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,703 ms / 4,000 ms
コード長 727 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 157,920 KB
最終ジャッジ日時 2024-12-25 13:06:11
合計ジャッジ時間 32,574 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush


N, M = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    g[a].append((b, c))
    g[b].append((a, c))
dist = [[1 << 60] * N for _ in range(3)]
dist[0][0] = dist[1][0] = 0
hq = []
heappush(hq, (0, 0, 0))
heappush(hq, (0, 0, 1))
while hq:
    d, v, k = heappop(hq)
    if k == 2 or dist[k][v] < d:
        continue
    for nv, c in g[v]:
        if d + c < dist[k][nv]:
            dist[k][nv] = d + c
            heappush(hq, (d + c, nv, k))
        if d < dist[k + 1][nv]:
            dist[k + 1][nv] = d
            heappush(hq, (d, nv, k + 1))
for i in range(N):
    print(dist[0][i] + dist[1][i])
0