結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー urunea
提出日時 2025-05-31 03:29:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,485 ms / 2,000 ms
コード長 729 bytes
コンパイル時間 777 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 159,912 KB
最終ジャッジ日時 2025-05-31 03:29:45
合計ジャッジ時間 30,567 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

N,M,P,Y=(int(x) for x in input().split())
d={}
for i in range(1,N+1):
    d[i] = []

for i in range(M):
    A,B,C=(int(x) for x in input().split())
    d[A].append([B,C])
    d[B].append([A,C])

shop={}
for i in range(P):
    D,E=(int(x) for x in input().split())
    shop[D] = E

inf=float("inf")
money_lose=[inf]*N
money_lose[0]=0
L=[[0,1]]
heapq.heapify(L)
while L:
    a=heapq.heappop(L)
    c=a[0]
    u=a[1]
    if c > money_lose[u-1]:
        continue

    for v, cost in d[u]:
        if money_lose[v-1] > c + cost:
            money_lose[v-1] = c + cost
            heapq.heappush(L,[c+cost, v])

ans=0
for i in range(N):
    if i+1 in shop:
        ans = max(ans, (Y-money_lose[i])//shop[i+1])

print(ans)
0