結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2020-04-02 22:45:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 121 ms / 5,000 ms |
コード長 | 1,086 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 80,000 KB |
最終ジャッジ日時 | 2024-06-28 15:22:26 |
合計ジャッジ時間 | 4,032 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import heapq def dijkstra(start: int, graph: list) -> list: """dijkstra法: 始点startから各頂点への最短距離を求める 計算量: O((E+V)logV) """ INF = 10 ** 18 n = len(graph) dist = [INF] * n dist[start] = 0 q = [(0, start)] # q = [(startからの距離, 現在地)] while q: d, v = heapq.heappop(q) if dist[v] < d: continue for nxt_v, cost in graph[v]: if dist[v] + cost < dist[nxt_v]: dist[nxt_v] = dist[v] + cost heapq.heappush(q, (dist[nxt_v], nxt_v)) return dist n, m, s, g = map(int, input().split()) info = [list(map(int, input().split())) for i in range(m)] graph = [[] for i in range(n)] for a, b, cost in info: graph[a].append((b, cost)) graph[b].append((a, cost)) dist = dijkstra(g, graph) ans = [s] v = s while True: if v == g: break tmp_v = 10 ** 18 for nxt_v, cost in graph[v]: if dist[v] == dist[nxt_v] + cost: tmp_v = min(tmp_v, nxt_v) v = tmp_v ans.append(v) print(*ans)