結果
問題 | No.807 umg tours |
ユーザー |
👑 |
提出日時 | 2022-04-17 15:43:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,658 ms / 4,000 ms |
コード長 | 714 bytes |
コンパイル時間 | 535 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 151,300 KB |
最終ジャッジ日時 | 2024-12-26 09:17:09 |
合計ジャッジ時間 | 25,243 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
from heapq import *n, m = map(int, input().split())edges = [[] for _ in range(n)]for _ in range(m):a, b, c = map(int, input().split())a -= 1b -= 1edges[a].append((b, c))edges[b].append((a, c))inf = 1 << 60dist = [[inf] * 2 for _ in range(n)]dist[0][0] = 0dist[0][1] = 0hq = [(0, 0, 0)]while hq:d, pos, t = heappop(hq)if d > dist[pos][t]:continuefor npos, c in edges[pos]:if dist[npos][t] > d + c:dist[npos][t] = d + cheappush(hq, (d + c, npos, t))if t == 0:if dist[npos][1] > d :dist[npos][1] = dheappush(hq, (d, npos, 1))for d1, d2 in dist:print(d1 + d2)