結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-01-25 13:47:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,112 ms / 2,000 ms |
コード長 | 587 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 178,432 KB |
最終ジャッジ日時 | 2025-01-25 22:59:21 |
合計ジャッジ時間 | 25,215 ms |
ジャッジサーバーID (参考情報) |
judge7 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
from collections import deque import heapq n,m,p,y=map(int,input().split()) edge=[list(map(int,input().split())) for _ in range(m)] shop=[list(map(int,input().split())) for _ in range(p)] E=[[] for _ in range(n+1)] for a,b,c in edge: E[a].append([b,c]) E[b].append([a,c]) ds=dict() for d,e in shop: ds[d]=e D=[0]*(n+1) D[1]=y H=[(-y,1)] while H: y,x=heapq.heappop(H) if -y<D[x]:continue for e,c in E[x]: if D[e]<max(0,D[x]-c): D[e]=max(0,D[x]-c) heapq.heappush(H,(-D[e],e)) ans=0 for i in range(1,n+1): if i in ds: ans=max(ans,D[i]//ds[i]) print(ans)