結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2022-05-23 19:16:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 829 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 243,832 KB |
最終ジャッジ日時 | 2024-09-20 13:20:36 |
合計ジャッジ時間 | 14,567 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 WA * 4 TLE * 2 -- * 9 |
ソースコード
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 = [float("inf")] * nwhile q:c, cut, x = heapq.heappop(q)c2[x] = min(c2[x], c)for y, cn in e[x]:if c2[y] < float("inf"):continueif cn > cut:heapq.heappush(q, (c+cut, cn, y))else:heapq.heappush(q, (c+cn, cut, y))for i in range(n):print(c1[i] + c2[i])