結果

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

ソースコード

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=[[1,0]]
heapq.heapify(L)
while L:
    a=heapq.heappop(L)
    u=a[0]
    c=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,[v, c+cost])

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