結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー D M
提出日時 2025-02-04 09:20:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,749 ms / 2,000 ms
コード長 2,204 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 172,192 KB
最終ジャッジ日時 2025-02-04 09:20:51
合計ジャッジ時間 36,830 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict
INF = pow(10, 20)  # 無限大とする値。距離や頂点数から考えて十分大きい値にすること

N, M,p,y = map(int, input().split())  # N:頂点数 M:入力辺数

edge = [set() for _ in range(N + 1)]  # edge[i]:頂点iから出ている辺

for i in range(M):
    A, B, C = map(int, input().split())  # A:出発元頂点番号 B:行先頂点番号 C:重み
    edge[A].add((B, C))  # (同一頂点に向かう辺は1本であることが問題文で保証されていない場合は、最短辺のみが残るように工夫すること)
    edge[B].add((A, C))  # 無向グラフなので逆側にも入れる

dist = [INF for _ in range(N + 1)]  # 始点から当該頂点までの最短距離。各頂点に対し無限大で初期化。
dist[1] = 0  # 始点から始点の距離なので当然0
prev_node = [-1 for _ in range(N + 1)]  # 始点から当該頂点までの最短距離時の直前頂点。各頂点に対し、prev(v)←無し。これを辿れば最短経路が求まる

hq = [(0, 1)]  # 優先度付きキューに(始点からの距離,始点の頂点番号)を追加
# ↑何を優先して探索させるかを十分に検討して、入れる要素の順番を決めること。間違えるとTLEする!!!

heapq.heapify(hq)

while len(hq) != 0:
    d, u = heapq.heappop(hq)  # 優先度付きキューから始点に近い側から頂点を取り出し
    if dist[u] == d:  # (Q(v)←altではなく、更新毎に追加しているので、不要パターンがある。最短の場合のみ処理)
        for v, C in edge[u]:  # 取り出した頂点から出ている全ての辺に対して
            new_d = d + C  # 新規の距離を計算し
            if dist[v] > new_d:  # 短くなっていたら更新
                dist[v] = new_d
                prev_node[v] = u
                heapq.heappush(hq, (new_d, v))  # 更新したところの接続点は短くなる可能性があるので再調査
D=defaultdict(int)
for _ in range(p):
    d,e=map(int,input().split())
    D[d]=e
ans=0
for i in range(1,N+1):
    if dist[i]!=INF and D[i]!=0:
        ans=max(ans,(y-dist[i])//D[i])
print(ans)
0