結果

問題 No.3013 ハチマキ買い星人
ユーザー hiro1729
提出日時 2025-01-25 12:42:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 793 ms / 2,000 ms
コード長 1,316 bytes
コンパイル時間 852 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 117,040 KB
最終ジャッジ日時 2025-01-25 22:17:30
合計ジャッジ時間 18,694 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
# sys.setrecursionlimit(10 ** 6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict as dd
from heapq import *
S = input
R = range
P = print
def I(): return int(S())
def M(): return map(int, S().split())
def L(): return list(M())
def O(): return list(map(int, open(0).read().split()))
def yn(b): print("Yes" if b else "No")
biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
smaa = "abcdefghijklmnopqrstuvwxyz"
ctoi = lambda c: ord(c) - ord('a')
ctoi2 = lambda c: ord(c) - ord('A')
itoc = lambda i: chr(ord('a') + i)
itoc2 = lambda i: chr(ord('A') + i)
inf = 10 ** 18
mod = 998244353
dxy4 = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dxy8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def acc(a):
	b = [0]
	for i in a:
		b.append(b[-1] + i)
	return b
def gin(N, M):
	g = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	return g

n,m,p,y=M()
g=[[]for _ in R(n)]
for _ in R(m):
	a,b,c=M();a-=1;b-=1;g[a].append((b,c));g[b].append((a,c))
d=[inf]*n;ok=[False]*n;q=[(0,0)];d[0]=0
while q:
	di,u=heappop(q)
	if ok[u]:continue
	ok[u]=True
	for v,c in g[u]:
		if di+c<d[v]:
			d[v]=di+c
			heappush(q,(d[v],v))
ans=0
for _ in R(p):
	D,e=M();D-=1
	ans=max(ans,(y-d[D])//e)
P(ans)
0