結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2022-05-23 18:48:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 859 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 142,352 KB |
最終ジャッジ日時 | 2024-09-20 13:20:09 |
合計ジャッジ時間 | 18,143 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 WA * 12 |
ソースコード
import heapqimport sysinput = sys.stdin.readlinen, m = map(int, input().split())e = [[] for _ in range(n)]for _ in range(m):ai, bi, ci = map(int, input().split())e[ai-1].append((bi-1, ci))e[bi-1].append((ai-1, ci))q = [(0, 0)]c1 = [None] * nwhile q:c, x = heapq.heappop(q)if c1[x] is not None:continuec1[x] = cfor y, cn in e[x]:if c1[y] is not None:continueheapq.heappush(q, (c+cn, y))q = [(0, 0, 0)]c2 = [None] * nwhile q:c, x, cut = heapq.heappop(q)if c2[x] is not None:continuec2[x] = (c, cut)for y, cn in e[x]:if c2[y] is not None:continueif cn > cut:heapq.heappush(q, (c+cut, y, cn))else:heapq.heappush(q, (c+cn, y, cut))for i in range(n):print(c1[i] + c2[i][0])