結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2022-05-22 15:09:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 99 ms / 5,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 78,208 KB |
最終ジャッジ日時 | 2024-09-20 12:37:23 |
合計ジャッジ時間 | 3,293 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline input_count = 0 N, M, START, GOAL = mi() G = {i:[] for i in range(N)} for i in range(M): A,B,C = mi() # Gの第三項に引き継ぎたいものを載せる # 何個目~ならi # 経路復元なら (A,B)など 行先だけ保存しておけばいいかも G[A].append((B, C)) G[B].append((A, C)) # V: 頂点数 # g[v] = {(w, cost)}: # 頂点vから遷移可能な頂点(w)とそのコスト(cost) # r: 始点の頂点 from heapq import heappush, heappop INF = 1<<55 dist = [INF] * N def dijkstra(N, G, s): que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist d1 = dijkstra(N, G, GOAL) ret = [] now = START while now!=GOAL: mins = INF ret.append(now) for v,c in G[now]: if dist[v] + c == dist[now]: mins = min(mins, v) now = mins ret.append(GOAL) print(*ret)