結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2017-05-27 15:17:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 112 ms / 5,000 ms |
コード長 | 1,178 bytes |
コンパイル時間 | 326 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-09-21 14:34:40 |
合計ジャッジ時間 | 2,466 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import sys from heapq import heappush, heappop inf = 1<<30 def solve(): N, M, S, G = map(int, input().split()) Adj = [[] for i in range(N)] for i in range(M): ai, bi, ci = map(int, input().split()) Adj[ai].append((bi, ci)) Adj[bi].append((ai, ci)) d, p = dijkstra(N, Adj, G) path = [S] dfs(d, Adj, S, G, path) print(*path) def dfs(d, Adj, v, G, path): if v == G: return nv = inf for u, c in Adj[v]: if d[v] - c == d[u] and u < nv: nv = u path.append(nv) dfs(d, Adj, nv, G, path) def dijkstra(N, Adj, s): d = [inf] * N p = [inf] * N visited = [False] * N d[s] = 0 p[s] = s pq = [(0, s)] for i in range(N): while pq: di, v = heappop(pq) if not visited[v] and di == d[v]: break visited[v] = True for u, c in Adj[v]: if d[v] + c < d[u]: d[u] = d[v] + c p[u] = v heappush(pq, (d[u], u)) elif d[v] + c == d[u] and v < p[u]: p[u] = v return d, p if __name__ == '__main__': solve()