結果

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

ソースコード

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(edges, num_node):
    """ 経路の表現
            [終点, 辺の値]
            A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf')] * num_node    #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートは0で初期化

    node_name = []
    heappush(node_name, [0, 0])

    while len(node_name) > 0:
        #ヒープから取り出し
        _, min_point = heappop(node_name)
        
        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in edges[min_point]:
            goal = factor[0]   #終点
            cost  = factor[1]   #コスト

            #更新条件
            if node[min_point] + cost < node[goal]:
                node[goal] = node[min_point] + cost     #更新
                #ヒープに登録
                heappush(node_name, [node[min_point] + cost, goal])

    return node


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=dijkstra(G, N)

ans=0

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

print(ans)
0