結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-02-08 16:33:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 689 ms / 2,000 ms |
コード長 | 487 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 147,200 KB |
最終ジャッジ日時 | 2025-02-08 16:33:31 |
合計ジャッジ時間 | 19,880 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
from heapq import* n,m,p,y=map(int,input().split()) abc=[[*map(int,input().split())]for _ in range(m)] de=[[*map(int,input().split())]for _ in range(p)] g=[[]for _ in range(n)] for a,b,c in abc: g[a-1]+=(b-1,c), g[b-1]+=(a-1,c), INF=1<<60 h=[INF]*n for d,e in de: h[d-1]=e q=[(-y,0)] s=[INF]*n s[0]=-y ans=0 while q: c,p=heappop(q) if s[p]<c: continue ans=max(ans,-c//h[p]) for v,nc in g[p]: if s[v]>s[p]+nc: s[v]=s[p]+nc heappush(q,(s[v],v)) print(ans)