結果

問題 No.3013 ハチマキ買い星人
ユーザー さわーくりーむおにおん🧅
提出日時 2025-01-26 17:13:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,980 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 164,128 KB
最終ジャッジ日時 2025-01-26 17:15:31
合計ジャッジ時間 133,439 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 43
権限があれば一括ダウンロードができます

ソースコード

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 = [i for i in range(num_node)]     #ノードの名前を0~ノードの数で表す

    while len(node_name) > 0:
        r = node_name[0]

        #最もコストが小さい頂点を探す
        for i in node_name:
            if  node[i] < node[r]:
                r = i   #コストが小さい頂点が見つかると更新

        #最もコストが小さい頂点を取り出す
        min_point = node_name.pop(node_name.index(r))

        #経路の要素を各変数に格納することで，視覚的に見やすくする
        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     #更新

    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