結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
|
提出日時 | 2024-12-04 13:54:00 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 544 bytes |
コンパイル時間 | 422 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 106,140 KB |
最終ジャッジ日時 | 2024-12-04 13:54:25 |
合計ジャッジ時間 | 21,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 WA * 30 |
ソースコード
import heapq n,m=map(int,input().split()) a=[[]for _ in range(m)] for _ in range(m): s,t,d=map(int,input().split()) s,t=s-1,t-1 a[s].append((t,d)) a[t].append((s,d)) q=[] heapq.heapify(q) heapq.heappush(q,(-10**18,0,0)) dist=[0]*n dist[0]=10**18 distt=[0]*n while q: dis,now,distanc=heapq.heappop(q) dis=-dis if dis<dist[now]: continue distt[now]=distanc for next,ndi in a[now]: v=min(dis,ndi) if dist[next]>=v: continue dist[next]=v heapq.heappush(q,(-v,next,distanc+1)) print(dist[n-1],distt[n-1])