結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー SourCreamOnion
提出日時 2025-01-26 17:44:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,320 bytes
コンパイル時間 922 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 354,548 KB
最終ジャッジ日時 2025-01-26 17:46:17
合計ジャッジ時間 98,194 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 9 TLE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate, combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from operator import itemgetter
import math
from heapq import heapify, heappush, heappop

LMI=lambda:list(map(int, input().split()))
LMS=lambda:list(map(str, input().split()))
MI=lambda:map(int, input().split())
MS=lambda:map(str, input().split())
II=lambda:int(input())
IS=lambda:input().split()
LI=lambda:list(input())
INF=10**18

def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        node, cost = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for node2, cost2 in links[node]:
            if node2 not in visited:
                heappush(heap, (node2, cost + cost2))
    return float('inf')


N,M,P,Y=MI()

G=[[] for i in range(N)]
Shop=[]
for i in range(M):
    a,b,c=MI()
    a-=1
    b-=1
    G[a].append((b, c))
    G[b].append((a, c))

for i in range(P):
    d, e=MI()
    Shop.append([d, e])

result=[]
for i in range(N):
    result.append(dijkstra(0, i, G))

ans=0

for de in Shop:
    ans=max(ans, max(0, Y-result[de[0]-1])//de[1])

print(ans)
0