結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー ナナフシモドキ
提出日時 2025-01-25 13:30:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,670 ms / 2,000 ms
コード長 757 bytes
コンパイル時間 507 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 157,328 KB
最終ジャッジ日時 2025-01-25 22:49:34
合計ジャッジ時間 32,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import queue

N , M , Q , Y = map( int , input().split() )

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

INF = 10**20
P = [ INF ] * N
for _ in range(Q) :
    d , e = map( int , input().split() )
    P[d-1] = e

check = [ True ] * N
num = [ 0 ] * N
dis = [ -1 ] * N

num[0] = Y // P[0]
dis[0] = 0

s = []
heapq.heappush( s , [ 0 , 0 ] )

while len(s) != 0 :
    d , p = heapq.heappop( s )
    if check[p] :
        dis[p] = d
        num[p] = ( Y - d ) // P[p]
        check[p] = False
        for q , c  in R[p] :
            if check[q] :
                heapq.heappush( s , [ d + c , q ] )
                
print( max(num) )
0