概要

この問題は、重み付き無向グラフにおいて、駅 \(1\) から駅 \(N\) への最短経路（最小運賃）を求め、その結果が予算 \(K\) 以内であるかを確認する問題です。

考察

この問題を解くためのポイントは以下の \(2\) 点です。

1. 最短経路問題への帰着 「運賃の合計が \(K\) 円以下であるものが存在するか判定し、その最小値を求める」という条件がありますが、これはまず駅 \(1\) から駅 \(N\) への最小運賃を求め、その結果が \(K\) 以下であるかを確認すればよいということになります。最小の運賃で予算を超えてしまう場合は、どのような経路を通っても予算を超えるためです。

2. 適切なアルゴリズムの選択 各路線の運賃（エッジの重み）はすべて \(1\) 以上の正の整数です。このように「重みが非負のグラフにおける単一始点最短経路問題」を解くには、ダイクストラ法が最適です。

   • 幅優先探索（BFS）はすべてのエッジの重みが同じ（例：すべて \(1\)）場合にしか使えません。
   • ベルマンフォード法でも解けますが、計算量が \(O(NM)\) となり、今回の制約（\(N=10^5, M=2 \times 10^5\)）では実行時間制限に間に合いません。

アルゴリズム

ダイクストラ法を用いて、以下の手順で解きます。

1. グラフの構築: 各駅を頂点、各路線を辺とする隣接リストを作成します。双方向に移動可能であるため、各路線 \((U_i, V_i, C_i)\) に対して \(U_i \to V_i\) と \(V_i \to U_i\) の両方の情報を格納します。
2. 初期化:
   • 駅 \(1\) から各駅への最小運賃を保持する配列 dist を用意し、すべて無限大（\(\infty\)）で初期化します。
   • dist[1] = 0 とします。
   • 優先度付きキュー（Priority Queue）を用意し、(運賃 0, 駅 1) を追加します。
3. 探索:
   • 優先度付きキューから「現在の運賃が最小の駅」を取り出します。
   • 取り出した駅の運賃が、既に記録されている dist の値より大きい場合は無視します。
   • その駅から隣接する各駅へ移動した場合の合計運賃を計算し、それが現在の dist よりも小さければ更新し、優先度付きキューに追加します。
4. 判定:
   • 探索終了後、dist[N] が \(K\) 以下であればその値を出力し、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  • ダイクストラ法において、各辺を最大 \(1\) 回ずつ調べ、優先度付きキューの操作に \(\log N\) かかるため、全体で \(O(M \log N)\) となります。今回の制約では十分高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(M\) 本の路線の情報を格納し、距離配列に \(N\) 個の要素を格納するため、 \(O(N + M)\) となります。

実装のポイント

• 高速な入出力: \(M\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 優先度付きキュー: Python の heapq モジュールは最小ヒープを提供しているため、(コスト, 頂点) のタプルを格納することで、常に最小コストの頂点を効率よく取り出すことができます。

• 早期終了: 優先度付きキューから取り出した時点の運賃が既に予算 \(K\) を超えている場合、その先の探索をスキップする枝刈りを行うことで、無駄な計算を省くことができます。

  ソースコード

import sys
import heapq

def solve():
    # 入力をすべて読み込み、イテレータを使用して高速に処理する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        n = int(next(it))
        m = int(next(it))
        k = int(next(it))
    except StopIteration:
        return
    
    # 隣接リスト形式でグラフを構築（双方向）
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        try:
            u = int(next(it))
            v = int(next(it))
            c = int(next(it))
            adj[u].append((v, c))
            adj[v].append((u, c))
        except StopIteration:
            break
            
    # ダイクストラ法を用いて駅1から各駅への最小運賃を求める
    # dist[i] は駅1から駅iまでの最小運賃を格納する
    inf = float('inf')
    dist = [inf] * (n + 1)
    dist[1] = 0
    
    # 優先度付きキュー (現在の合計運賃, 駅番号)
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに記録されている最短距離より大きい場合はスキップ
        if d > dist[u]:
            continue
        
        # 現在の運賃がすでに予算 K を超えている場合、この経路をさらに進めても予算内に収まらない
        if d > k:
            continue
            
        # 隣接する駅を探索
        for v, cost in adj[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    # 駅Nまでの最小運賃を取得
    ans = dist[n]
    
    # 最小運賃が予算 K 以下であるか判定
    if ans <= k:
        print(ans)
    else:
        print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。