結果

問題 No.3013 ハチマキ買い星人
ユーザー prin_kemkem
提出日時 2025-01-25 13:04:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 767 ms / 2,000 ms
コード長 1,370 bytes
コンパイル時間 668 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 118,148 KB
最終ジャッジ日時 2025-01-25 22:32:13
合計ジャッジ時間 17,091 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
# from functools import cache
# import copy
from itertools import combinations, permutations, product, accumulate, groupby, chain
# from more_itertools import distinct_permutations
from heapq import heapify, heappop, heappush, heappushpop
import math
import bisect
# from pprint import pprint
from random import randint, shuffle, randrange
# from sortedcontainers import SortedSet, SortedList, SortedDict
import sys
# sys.setrecursionlimit(2000000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################   

N, M, P, Y = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    adj[a].append((b, c))
    adj[b].append((a, c))

def dijkstra(s):
    dist = [inf]*N
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, now = heappop(hq)
        if d > dist[now]: continue
        for next, cost in adj[now]:
            nd = d+cost
            if dist[next] <= nd: continue
            dist[next] = nd
            heappush(hq, (nd, next)) 
    return dist

dist = dijkstra(0)
ans = 0
for _ in range(P):
    d, e = map(int, input().split())
    d -= 1
    ans = max(ans, max(Y-dist[d], 0)//e)
print(ans)
0