概要

この問題は、コスト制限付きの最短経路問題です。無向グラフにおいて、始点から終点までの経路で、辺の重みの合計が \(K\) 以下となるもののうち、最小のものを求めます。

考察

この問題は典型的な「コスト制限付き最短経路探索」の問題です。素朴な方法として、全探索を行うことを考えますが、頂点数 \(N\) が最大 \(10^5\)、辺数 \(M\) も最大 \(2 \times 10^5\) なので、単純な全探索やDFSでは計算量が大きすぎて間に合いません。

また、同じ駅を複数回通ることが許されているため、単純な訪問済みフラグ管理では対応できません。さらに、運賃の上限 \(K\) が最大 \(10^9\) であるため、DPの状態にコストを持たせることも現実的ではありません（メモリも時間も足りない）。

そこで、ダイクストラ法を用いることを考えます。ダイクストラ法は非負の重みを持つグラフにおける単一始点最短経路を効率的に求めることができます。今回は「運賃の合計が \(K\) 円以下」という条件があるため、ダイクストラ法の更新時に new_cost <= K の条件を追加することで、制約を満たす範囲でのみ探索を行います。

これにより、無駄な探索を避けつつ、最小の運賃で目的地に到達できる経路を見つけ出すことができます。

アルゴリズム

1. グラフ構築:

   • 各辺情報を双方向にグラフに格納します。Pythonでは隣接リスト表現を使用します。

2. ダイクストラ法の適用:

   • 始点（駅1）からの最小運賃を記録する配列 dist を用意し、初期値は無限大（INF）、始点のみ0に設定。
   • 優先度付きキュー（ヒープ）を使って、(現在の運賃, 現在の駅) の形で探索します。
   • キューから取り出したノードについて、隣接ノードへの遷移を考えます。
   • 新しい運賃が予算 \(K\) を超える場合は無視。
   • 新しい運賃がこれまでの記録より小さければ更新し、ヒープに追加。

3. 結果の出力:

   • 終点（駅 \(N\)）の dist が更新されていればその値を、そうでなければ -1 を出力します。

例：

入力例：

4 4 10
1 2 3
2 3 4
3 4 5
1 4 10

• 駅1 → 2 → 3 → 4：コスト \(3 + 4 + 5 = 12\)（予算超過）
• 駅1 → 4：コスト 10（OK） → 答えは 10

計算量

• 時間計算量: \(O(M \log N)\)
  • ダイクストラ法の典型計算量。各辺を最大1回処理し、ヒープ操作が \(\log N\)。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列による。

実装のポイント

• グラフの頂点番号は0-indexedに変換して扱う（入力が1-indexedのため）。
• ヒープには (cost, node) の順で格納し、コストの小さい順に取り出す。
• dist 配列の初期化は十分大きな値（例: \(10^{18}\)）にする。
• 更新条件に new_cost <= K を必ず含める。
• 同じノードへの複数の経路がある場合でも、既に最短が確定している場合はスキップする枝刈りを入れる。

## ソースコード

```python
import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    # グラフ構築
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        c = int(data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    # ダイクストラ法で最小運賃を求める（コスト制限付き）
    # dist[i] := 駅1から駅i+1へのコストK以下の最小運賃
    # 無限大で初期化
    INF = 10**18
    dist = [INF] * N
    dist[0] = 0
    # (現在の運賃, 現在の駅)
    pq = [(0, 0)]
    
    while pq:
        cost, u = heapq.heappop(pq)
        if cost > dist[u]:
            continue
        for v, c in graph[u]:
            new_cost = cost + c
            if new_cost <= K and new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(pq, (new_cost, v))
    
    result = dist[N-1] if dist[N-1] != INF else -1
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。