結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2017-10-24 19:39:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 134 ms / 5,000 ms |
コード長 | 870 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 79,940 KB |
最終ジャッジ日時 | 2024-11-21 17:47:47 |
合計ジャッジ時間 | 4,224 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
from queue import PriorityQueue N,M,S,G = list(map(int, input().split(' '))) C = [] for i in range(N): C.append([-1 for _ in range(N)]) for i in range(M): f,t,c = list(map(int, input().split(' '))) C[f][t] = c C[t][f] = c P = [] for i in range(N): P.append(-1) D = [] for i in range(N): D.append(float('inf')) D[G] = 0 Q = PriorityQueue() Q.put((0, G)) while not Q.empty(): d, f = Q.get() if D[f] < d: continue for t, c in enumerate(C[f]): if c != -1: nc = D[f] + c if nc < D[t]: D[t] = nc P[t] = f Q.put((D[t], t)) elif nc == D[t]: P[t] = min(P[t], f) s = S t = G solution = [] while s != t: solution.append(str(s)) s = P[s] solution.append(str(G)) print(' '.join(solution))