結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー u_kun
提出日時 2025-01-25 13:56:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 882 ms / 2,000 ms
コード長 1,964 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 126,888 KB
最終ジャッジ日時 2025-01-25 23:03:42
合計ジャッジ時間 21,517 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 『重みあり』の無向グラフの最短経路長問題 #
# ヒープを用いたダイクストラ法
import heapq

N, M, P, Y = map(int, input().split())
G = [[] for _ in range(N + 1)]  # 先頭はダミー (頂点 1 ~ 頂点 N)
for _ in range(M):
    u, v, c = map(int, input().split())
    G[u].append((v, c))
    G[v].append((u, c))
    
# 始点(頂点1)から各頂点への最小コストを保存する配列 (-1 は未訪問 )
dist = [-1 for _ in range(N + 1)]
dist[1] = 0

# ダイクストラ法で使うヒープ
Q = []

# 始点となる頂点1をヒープに追加　( その頂点まで行くのに要する暫定最小コスト, 頂点番号 ) として追加する
heapq.heappush(Q, (0, 1))

# ヒープから取り出したことがあるかを保存する配列
done = [False for _ in range(N + 1)]


# ダイクストラ法で各頂点への最小コストを求める
while Q:
    
    cost, from_id = heapq.heappop(Q)
    
    # 既にヒープから取り出したことがあればスキップ
    if done[from_id]:
        continue
    
    done[from_id] = True
    
    
    for to_id, path_cost in G[from_id]:
        # 探索先が未訪問か, あるいは訪問済みでも最短コストを更新できるなら更新！
        if dist[to_id] == -1 or dist[to_id] > dist[from_id] + path_cost:
            dist[to_id] = dist[from_id] + path_cost
            heapq.heappush(Q, (dist[to_id], to_id))


shopId_cost = {}
for _ in range(P):
    D, E = map(int, input().split())
    shopId_cost[D] = E

ans = 0
          
for i in range(1, N + 1): 
    if i in shopId_cost:
        cost = shopId_cost[i]  # ハチマキの値段
        
        if dist[i] != -1:
            have_money = Y - dist[i]
            
            if have_money <= 0:
                continue
            
            tmp_ans = have_money // cost
            
            ans = max(ans, tmp_ans)

print(ans)
0