結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2019-12-05 17:29:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 174 ms / 5,000 ms |
コード長 | 768 bytes |
コンパイル時間 | 418 ms |
コンパイル使用メモリ | 81,952 KB |
実行使用メモリ | 77,480 KB |
最終ジャッジ日時 | 2024-12-21 10:23:42 |
合計ジャッジ時間 | 5,538 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
def warshall_floyd(d): for k in range(N): for i in range(N): for j in range(N): d[i][j] = min(d[i][j], d[i][k]+d[k][j]) return d N, M, S, G = map(int, input().split()) d = [[10**18]*N for _ in range(N)] adj_list = [[] for _ in range(N)] for i in range(N): d[i][i] = 0 for _ in range(M): ai, bi, ci = map(int, input().split()) d[ai][bi] = ci d[bi][ai] = ci adj_list[ai].append((bi, ci)) adj_list[bi].append((ai, ci)) for i in range(N): adj_list[i].sort() d = warshall_floyd(d) ans = [S] while True: prev = ans[-1] for nv, w in adj_list[prev]: if w+d[nv][G]==d[prev][G]: ans.append(nv) break if ans[-1]==G: break print(*ans)