概要

直径が \(K\) 以上のトンネルだけを使って中継局 \(1\) から中継局 \(N\) へ到達できるか判定し、到達可能なら最小のトンネル本数（最短経路長）を求める問題です。

考察

重要な気づき

この問題では「すべてのトンネルの直径が \(K\) 以上である経路」という制約があります。これは言い換えると、直径が \(K\) 未満のトンネルはそもそも使えないということです。

つまり、\(M\) 本あるトンネルのうち、直径が \(K\) 以上のものだけを残した新しいグラフを考えれば、問題は単純な最短経路問題に帰着されます。

素朴なアプローチとの比較

もし「すべての経路を列挙して条件を満たすか確認する」というアプローチを取ると、経路数が指数的に増えるため到底間に合いません。しかし、使えるトンネルだけでグラフを構築すれば、辺の重みがすべて1（トンネル1本 = コスト1）の最短経路問題になります。

辺の重みがすべて等しい場合の最短経路問題は、BFS（幅優先探索） で \(O(N + M)\) で解くことができます。Dijkstra法を使う必要はありません。

アルゴリズム

1. グラフの構築: 各トンネルについて、直径 \(W_i \geq K\) であるもののみを辺として隣接リストに追加する。
2. BFS（幅優先探索）: 中継局 \(1\) を始点として BFS を行い、各頂点への最短距離（通過するトンネルの本数）を求める。
3. 結果の出力: 中継局 \(N\) に到達できた場合はその距離を、到達できなかった場合は \(-1\) を出力する。

具体例

例えば \(N = 4, K = 5\) で以下のトンネルがあるとします：

• \(1 \leftrightarrow 2\)（直径 \(10\)）→ \(10 \geq 5\) なので使える
• \(2 \leftrightarrow 4\)（直径 \(3\)）→ \(3 < 5\) なので使えない
• \(1 \leftrightarrow 3\)（直径 \(7\)）→ \(7 \geq 5\) なので使える
• \(3 \leftrightarrow 4\)（直径 \(6\)）→ \(6 \geq 5\) なので使える

使えるトンネルだけのグラフで BFS すると、\(1 \to 3 \to 4\) の経路が見つかり、答えは \(2\) です。

計算量

• 時間計算量: \(O(N + M)\)
  • グラフ構築に \(O(M)\)、BFS に \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、距離配列に \(O(N)\)

実装のポイント

• フィルタリングをグラフ構築時に行う: BFS の探索中に毎回 \(W_i \geq K\) をチェックするのではなく、グラフ構築の段階で条件を満たす辺だけを追加することで、コードがシンプルになります。

• BFS で頂点 \(N\) に到達した時点で即座に終了: BFS は始点から近い順に探索するため、頂点 \(N\) に初めて到達した時点でそれが最短距離です。早期終了により無駄な探索を省けます。

• sys.stdin.readline の使用: Python では入力が大量の場合に標準の input() は遅いため、sys.stdin.readline を使うことで高速化しています。

• deque の使用: BFS のキューには collections.deque を使います。リストの pop(0) は \(O(N)\) ですが、deque の popleft() は \(O(1)\) で動作します。

  ソースコード

from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        if w >= K:
            graph[u].append(v)
            graph[v].append(u)
    
    # BFS from node 1 to node N
    dist = [-1] * (N + 1)
    dist[1] = 0
    queue = deque([1])
    while queue:
        node = queue.popleft()
        if node == N:
            print(dist[N])
            return
        for nxt in graph[node]:
            if dist[nxt] == -1:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    
    print(-1)

main()

---

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