結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー YHz_ikiriAbu
提出日時 2025-04-19 00:34:09
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 3,069 ms / 5,000 ms
コード長 1,583 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 90,668 KB
最終ジャッジ日時 2025-04-19 00:35:34
合計ジャッジ時間 74,120 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import math
from collections import defaultdict

INF = math.inf
n, m, k = map(int, input().split())
c = list(map(int, input().split()))
bridge = []

# 隣接リストの構築
graph = defaultdict(list)
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append((v, c[_]))
    graph[v].append((u, c[_]))


def dijkstra(start):
    # 優先度付きキュー
    que = []
    heapq.heappush(que, (0, start, 0))  # (cost, now, coupon)
    visited = {}

    while que:
        cost, now, coupon = heapq.heappop(que)

        # 既に訪問済みで、より良いコストがない場合はスキップ
        if (now, coupon) in visited and visited[(now, coupon)] <= cost:
            continue
        visited[(now, coupon)] = cost

        # 隣接ノードを探索
        for next_node, edge_cost in graph[now]:
            # クーポンを使わない場合
            if (next_node, coupon) not in visited or visited[
                (next_node, coupon)
            ] > cost + edge_cost:
                heapq.heappush(que, (cost + edge_cost, next_node, coupon))

            # クーポンを使う場合
            if coupon < k and (
                (next_node, coupon + 1) not in visited
                or visited[(next_node, coupon + 1)] > cost
            ):
                heapq.heappush(que, (cost, next_node, coupon + 1))

    # 街Nに到達するための最小コストを探す
    result = min(visited.get((n, i), INF) for i in range(k + 1))
    return result


ans = dijkstra(1)
if ans == INF:
    print(-1)
else:
    print(ans)
0