結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
|
提出日時 | 2025-02-02 00:13:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,104 ms / 2,000 ms |
コード長 | 635 bytes |
コンパイル時間 | 1,088 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 114,408 KB |
最終ジャッジ日時 | 2025-02-02 00:14:12 |
合計ジャッジ時間 | 25,408 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
N,M,P,Y=map(int,input().split()) con=[[] for _ in range(N)] for _ in range(M): A,B,C=map(int,input().split()) ; A-=1 ; B-=1 con[A].append((B,C)) con[B].append((A,C)) from heapq import heappush,heappop def dijkstra(start): inf=1<<60 ; re=[inf for _ in range(len(con))] ; re[start]=0 q=[] ; heappush(q,(0,start)) while q: d,e=heappop(q) if re[e]<d : continue for aim,pd in con[e]: if d+pd<re[aim] : heappush(q,(d+pd,aim)) ; re[aim]=d+pd return re dist=dijkstra(0) ans=0 for _ in range(P): A,B=map(int,input().split()) ; A-=1 ans=max(ans,(Y-dist[A])//B) print(ans)