結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー kakur41
提出日時 2025-04-20 14:13:40
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,684 ms / 5,000 ms
コード長 3,793 bytes
コンパイル時間 549 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 68,444 KB
最終ジャッジ日時 2025-04-20 14:14:36
合計ジャッジ時間 38,325 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import sys

# 標準入力の高速化 (必要な場合)
# input = sys.stdin.readline

def solve():
    """問題を解くメイン関数"""
    N, M, K = map(int, sys.stdin.readline().split())
    # M本の橋のコストをリストとして読み込む
    edges_cost = list(map(int, sys.stdin.readline().split()))

    # グラフを隣接リストで表現
    # graph[u] には (v, cost) のタプルのリストが入る
    # u: 現在の町, v: 隣接する町, cost: 橋のコスト
    graph = [[] for _ in range(N)]
    for i in range(M):
        # 橋の両端の町を読み込む
        u, v = map(int, sys.stdin.readline().split())
        # 0-indexed に調整
        u -= 1
        v -= 1
        # i番目の橋のコストを取得
        cost = edges_cost[i]
        # 無向グラフなので両方向のエッジを追加
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    # 距離配列の初期化
    # dist[i][k] は、町iにクーポンをk枚使って到達するための最小コスト
    # 十分に大きい値 (無限大) で初期化する
    INF = float('inf')
    dist = [[INF] * (K + 1) for _ in range(N)]

    # 優先度付きキュー (最小ヒープ) の初期化
    # 要素は (現在のコスト, 現在の町, 使ったクーポン数) のタプル
    pq = [(0, 0, 0)] # スタート地点 (町1 = 0-indexed, コスト0, クーポン使用0枚)
    dist[0][0] = 0   # スタート地点のコストを0に設定

    # ダイクストラ法の開始
    while pq:
        # 現在最もコストが小さい状態を取り出す
        current_cost, u, k_used = heapq.heappop(pq)

        # 取り出した状態のコストが、記録されている最小コストより大きい場合は、
        # より効率的な経路がすでに見つかっているのでスキップする
        if current_cost > dist[u][k_used]:
            continue

        # 現在の町uから移動可能な隣接町vへの遷移を調べる
        for v, cost in graph[u]:
            # --- ケース1: クーポンを使わずに橋を渡る ---
            new_cost_no_coupon = current_cost + cost
            # より小さいコストで町vに到達できる場合
            if new_cost_no_coupon < dist[v][k_used]:
                # 最小コストを更新
                dist[v][k_used] = new_cost_no_coupon
                # 新しい状態を優先度付きキューに追加
                heapq.heappush(pq, (new_cost_no_coupon, v, k_used))

            # --- ケース2: クーポンを使って橋を渡る ---
            # クーポンがまだ残っている場合 (k_used < K)
            if k_used < K:
                # クーポンを使うので、コストは現在のコストのまま (current_cost)
                new_cost_with_coupon = current_cost
                # クーポン使用後の状態 (町v, クーポン使用数 k_used + 1) のコストを確認
                # より小さいコストで到達できる場合
                if new_cost_with_coupon < dist[v][k_used + 1]:
                    # 最小コストを更新
                    dist[v][k_used + 1] = new_cost_with_coupon
                    # 新しい状態を優先度付きキューに追加
                    heapq.heappush(pq, (new_cost_with_coupon, v, k_used + 1))

    # 町N (0-indexedでは N-1) に到達するための最小コストを計算
    # クーポンを0枚からK枚まで使った場合のコストのうち、最も小さいものを探す
    min_cost_to_N = min(dist[N - 1])

    # 結果の出力
    # 最小コストがINFのままなら到達不可能
    if min_cost_to_N == INF:
        print(-1)
    else:
        print(min_cost_to_N)

# 関数を実行
solve()
0