結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2022-03-30 01:19:50 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 134 ms / 5,000 ms |
コード長 | 636 bytes |
コンパイル時間 | 86 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 14,336 KB |
最終ジャッジ日時 | 2024-11-09 00:38:51 |
合計ジャッジ時間 | 2,493 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
from heapq import heappop,heappush N,M,S,G=map(int,input().split()) E=[[] for i in range(N+1)] for i in range(M): a,b,c=map(int,input().split()) E[a].append((b,c)) E[b].append((a,c)) D=[1<<30]*(N+1) FROM=[-1]*(N+1) D[G]=0 Q=[] Q.append((0,G)) while Q: time,now=heappop(Q) if D[now]!=time: continue for to,cost in E[now]: if D[to]>time+cost: D[to]=time+cost heappush(Q,(D[to],to)) FROM[to]=now elif D[to]==time+cost: FROM[to]=min(FROM[to],now) now=S ANS=[S] while now!=G: now=FROM[now] ANS.append(now) print(*ANS)