概要

駅 \(1\) から駅 \(N\) までの運賃合計の最小値（最短距離）を求め、さらにそれが予算 \(K\) 円以下ならその値を、超えるなら -1 を出力する問題です。

考察

• 各路線には運賃 \(C_i\) があり、これは「辺の重み（コスト）」とみなせます。駅は「頂点」、路線は「無向辺」の重み付きグラフになります。
• 同じ駅を複数回通ってよいですが、運賃はすべて正（\(C_i \ge 1\)）なので、無駄に遠回りするほどコストは増えます。したがって「駅 \(1\) から駅 \(N\) への最小運賃」は、通常の最短経路問題として定義できます。

素朴な方法が難しい理由

• 「予算 \(K\) 以下の経路が存在するか」を、DFS/BFSのように経路を列挙して調べると、分岐が多いグラフでは経路数が爆発します（同じ駅を何度でも通れるので特に危険）。現実的な時間では終わりません（TLE）。
• BFSは辺の本数（移動回数）が最小の経路は求められますが、今回は「運賃合計」が最小であり、辺重みがあるためBFSでは正しく答えが出ません（WA）。

解決方針

• 辺重みがすべて正なので、最短経路には ダイクストラ法 が使えます。
• さらに今回は「\(K\) 円以下」という上限があるので、
  • 距離（運賃合計）が \(K\) を超えた状態は探索しても意味がない（そこから先は必ず \(K\) 超えのまま）
    という性質を利用して探索を打ち切ったり、遷移を抑制できます。

アルゴリズム

ダイクストラ法で駅 \(1\) からの最小運賃 dist[v] を求めます。

1. 隣接リストでグラフを構築する（\(N\) が大きいので行列は不可）。
2. dist[1]=0、それ以外は十分大きい値（INF）で初期化。
3. 優先度付きキュー（最小ヒープ）に (0, 1) を入れる。
4. ヒープから「現時点で最小の運賃 d の駅 u」を取り出し、以下を行う：
   • 取り出した (d,u) が古い情報なら無視（d != dist[u]）。
   • d > K なら、以降取り出される d はさらに大きいので探索を終了（到達不可能）。
   • u == N なら、ダイクストラ法の性質により d が最小運賃なので出力して終了。
   • 隣接する辺 \((u \to v)\) の運賃 \(w\) について nd = d + w を計算し、
     • nd <= K かつ nd < dist[v] のときのみ更新してヒープに入れる。
5. 最後まで駅 \(N\) が確定しなければ -1。

この「駅 \(N\) をヒープから取り出した瞬間に答えが確定する」点が、ダイクストラ法の重要な性質です（正の重みのみのため）。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （ダイクストラ法。nd <= K の枝刈りにより実際はさらに小さくなることがあります）
• 空間計算量: \(O(N+M)\)
  （隣接リストと距離配列、ヒープ）

実装のポイント

• INF は最大でも \(10^9\) の運賃が最大 \(10^5\) 回足されうるので、十分大きく 10**30 などにします。

• if d != dist[u]: continue を入れて、ヒープ内の古い状態（更新前の距離）を捨てないと無駄な処理が増えます。

• d > K で break できるのは、ヒープから取り出す d が常に非減少（最小から順）だからです。

• 遷移時に nd <= K を条件に入れておくと、予算超過の状態をヒープに積まずに済み、高速化します。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        g[u].append((v, c))
        g[v].append((u, c))

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    hq = [(0, 1)]

    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if d > K:
            break
        if u == N:
            print(d)
            return
        for v, w in g[u]:
            nd = d + w
            if nd <= K and nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    print(-1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。