結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2023-06-27 21:15:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 834 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 77,568 KB |
最終ジャッジ日時 | 2024-07-04 13:47:17 |
合計ジャッジ時間 | 3,499 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 18 |
ソースコード
from collections import defaultdictfrom heapq import heapify, heappop, heappushn, m, s, g = map(int, input().split())G = defaultdict(list)for _ in range(m):a, b, c = map(int, input().split())G[a].append((b, c))G[b].append((a, c))for i in range(n):G[i].sort(key=lambda x: x[0])INF = 10**18DP = [INF for _ in range(n)]DP[s] = 0H = [(0, s)]while H:cc, cp = heappop(H)if cc > DP[cp]:continueif cp == g:breakfor np, dc in G[cp]:nc = cc + dcif nc >= DP[np]:continueDP[np] = ncheappush(H, (nc, np))ANS = [g]res = DP[g]while ANS[-1] != s:cp = ANS[-1]for np, dc in G[cp]:nc = res - dcif nc == DP[np]:ANS.append(np)res -= dcbreakANS.reverse()print(*ANS)