結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2022-05-18 09:57:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 834 bytes |
コンパイル時間 | 365 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 114,124 KB |
最終ジャッジ日時 | 2024-09-16 10:43:58 |
合計ジャッジ時間 | 15,165 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 20 TLE * 1 -- * 1 |
ソースコード
from heapq import heappush, heappopINF = float('inf')N, M = map(int, input().split())adj = [[] for _ in range(N)]for i in range(M):s, t, d = map(int, input().split())s -= 1t -= 1adj[s].append((t, d))adj[t].append((s, d))def dijkstra(s, n):dist = [INF] * nhq = [(0, s)]dist[s] = 0seen = [False] * n# 経路復元用# prev = [-1]*nwhile hq:v = heappop(hq)[1]seen[v] = Truefor to, cost in adj[v]:if seen[to] == False and dist[v] + cost < dist[to]:dist[to] = dist[v] + cost# prev[to] = vheappush(hq, (dist[to], to))return distd = dijkstra(0, N)print(0)for i in range(1,N):res = float('inf')for b, c in adj[i]:res = min(res, d[b], c)print(res+d[i])