結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー akazuki8
提出日時 2025-09-12 04:16:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 901 ms / 2,000 ms
コード長 935 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 118,984 KB
最終ジャッジ日時 2025-09-12 04:17:15
合計ジャッジ時間 23,041 ms
ジャッジサーバーID
（参考情報） 		judge / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def dijkstra(graph, start=0):
    num_node = len(graph)
    inf = float('inf')
    distances = [inf] * num_node
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

n,m,p,y=map(int,input().split())
a=[[]for _ in range(n)]
for i in range(m):
	s,t,u=map(int,input().split())
	a[s-1].append((t-1,u))
	a[t-1].append((s-1,u))
b=[-1 for i in range(n)]
for i in range(p):
	s,t=map(int,input().split())
	b[s-1]=t
x=dijkstra(a)
ans=0
for i in range(n):
	if b[i]!=-1:
		ans=max(ans,max(0,y-x[i])//b[i])
print(ans)
0