概要

重み付き無向グラフにおいて、駅 \(1\) から駅 \(N\) への最短経路を求め、その運賃が予算 \(K\) 円以下かどうかを判定する問題です。

考察

• 重要な気づき: 「運賃の合計が \(K\) 円以下で最小のもの」を求めるには、まず駅 \(1\) から駅 \(N\) への最短経路（運賃合計が最小の経路）を求めれば十分です。最短経路の運賃が \(K\) 以下ならそれが答えであり、最短経路ですら \(K\) を超えるなら、他のどの経路でも \(K\) 以下にはなりません。

• 素朴なアプローチ（BFS など）: 辺の重みがすべて同じであれば幅優先探索（BFS）で最短経路を求められますが、本問題では各路線の運賃 \(C_i\) が異なるため、BFS では正しい最短経路を求められません。

• 解決策: 重みが非負の辺を持つグラフでの最短経路問題には、ダイクストラ法（Dijkstra’s algorithm） が適しています。\(C_i \geq 1\) なので非負条件を満たしており、ダイクストラ法が正しく動作します。

アルゴリズム

1. グラフの構築: 入力から隣接リストを作成します。各駅 \(U_i, V_i\) を双方向の辺（運賃 \(C_i\)）で結びます。

2. ダイクストラ法で最短距離を計算:

   • 距離配列 dist を用意し、dist[1] = 0、それ以外は \(\infty\) で初期化します。
   • 優先度付きキュー（最小ヒープ）に (0, 1)（距離 \(0\)、駅 \(1\)）を入れます。
   • ヒープから距離が最小の頂点 \(u\) を取り出し、\(u\) の隣接頂点 \(v\) について「\(u\) 経由の距離 \(d + c\) が dist[v] より小さければ更新してヒープに追加」を繰り返します。
   • 頂点 \(N\) を取り出した時点で早期終了できます（その時点で dist[N] が確定しているため）。

3. 判定と出力:

   • dist[N] \(\leq K\) なら dist[N] を出力します。
   • dist[N] が \(\infty\)（到達不可能）または \(K\) を超える場合は -1 を出力します。

具体例（\(N=3, M=3, K=5\) のとき）:

辺: 1-2 (運賃3), 2-3 (運賃2), 1-3 (運賃6)

• 経路 \(1 \to 2 \to 3\): 運賃 \(3 + 2 = 5\)（\(\leq K\)）
• 経路 \(1 \to 3\): 運賃 \(6\)（\(> K\)）
• 最短は \(5\) で予算以内なので、答えは \(5\)。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量です。ヒープ操作が \(O(\log N)\) で、各辺について最大1回のヒープ挿入が行われます。
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、距離配列に \(O(N)\)、ヒープに最大 \(O(M)\) の要素が入ります。

実装のポイント

• sys.stdin.buffer.read() による高速入力: Python では標準入力の読み込みが遅くなりがちなので、一括読み込みで高速化しています。

• ヒープからの取り出し時の重複チェック: if d > dist[u]: continue により、既により短い距離で確定済みの頂点を再処理しないようにしています。これがないと計算量が悪化します。

• 早期終了: 頂点 \(N\) がヒープから取り出された時点で最短距離が確定するため、if u == N: break で無駄な探索を省きます。

• 運賃 \(C_i\) が最大 \(10^9\)、辺数が最大 \(2 \times 10^5\) あるため、最短距離は最大で約 \(10^{14}\) 程度になり得ます。Python では整数のオーバーフローがないため特別な対処は不要ですが、他の言語では long long 型を使う必要があります。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for i in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        graph[U].append((V, C))
        graph[V].append((U, C))
    
    # Dijkstra's algorithm from node 1 to node N
    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
        if u == N:
            break
        for v, c in graph[u]:
            nd = d + c
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    if dist[N] <= K:
        print(dist[N])
    else:
        print(-1)

main()

この解説は claude4.6opus-thinking によって生成されました。