結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2024-07-18 23:28:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 5,000 ms |
コード長 | 755 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 77,492 KB |
最終ジャッジ日時 | 2024-07-18 23:28:55 |
合計ジャッジ時間 | 3,875 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
from collections import defaultdict, dequeINF = 1 << 60N, M, S, G = map(int, input().split())adj = defaultdict(list)for _ in range(M):a, b, c = map(int, input().split())adj[a].append((b, c))adj[b].append((a, c))dists = [INF] * Nq = deque([(0, G)]) # ゴールから探索するwhile q:d, v = q.popleft()if dists[v] <= d: continuedists[v] = dfor to, cost in adj[v]:if dists[to] <= d + cost: continueq.append((d+cost, to))# 経路復元path = [S] # スタート地点から復元while (v := path[-1]) != G:nv = INF # 次の頂点for to, cost in adj[v]:if dists[to]+cost == dists[v]:nv = min(nv, to)assert nv != INFpath.append(nv)print(*path)