結果

問題 No.3013 ハチマキ買い星人
ユーザー titia
提出日時 2025-02-01 05:04:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,097 ms / 2,000 ms
コード長 609 bytes
コンパイル時間 1,152 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 116,248 KB
最終ジャッジ日時 2025-02-01 05:05:20
合計ジャッジ時間 27,224 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M,P,Y=map(int,input().split())
E=[[] for i in range(N)]

for i in range(M):
    a,b,c=map(int,input().split())
    a-=1
    b-=1

    E[a].append((b,c))
    E[b].append((a,c))

LIST=[1<<60]*N

for i in range(P):
    d,e=map(int,input().split())
    LIST[d-1]=e

from heapq import heappop,heappush

DIS=[1<<60]*N
DIS[0]=0
Q=[(0,0)]

while Q:
    dis,now=heappop(Q)

    if DIS[now]!=dis:
        continue

    for to,cost in E[now]:
        if DIS[to]>cost+dis:
            DIS[to]=cost+dis
            heappush(Q,(DIS[to],to))
    
ANS=0

for i in range(N):
    ANS=max(ANS,(Y-DIS[i])//LIST[i])

print(ANS)
0