概要

この問題は、与えられた条件（トンネルの直径が \(K\) 以上）を満たす道のみを使用して、地点 1 から地点 \(N\) までの最短経路（通過する辺の数の最小値）を求める問題です。

考察

この問題を解くための重要なポイントは以下の2点です。

1. 条件を満たさない辺の除外 問題文には「経路上のすべてのトンネルの直径が \(K\) 以上である必要がある」とあります。つまり、直径 \(W_i\) が \(K\) 未満であるトンネルは、今回の経路には一切使えません。したがって、グラフを構築する際に \(W_i < K\) の辺を最初から無視することで、条件を単純化できます。

2. 最短経路の算出 「通過するトンネルの本数をできるだけ少なくしたい」という要求は、グラフ理論における「未加重グラフの最短経路問題」に相当します。すべての辺のコストが 1（トンネル 1 本）であるため、ダイクストラ法のような複雑なアルゴリズムを使わなくても、幅優先探索 (BFS) を用いることで効率的に最短距離を求めることができます。

もし、すべての探索を終えても地点 \(N\) に到達できない場合は、経路が存在しないということなので -1 を出力します。

アルゴリズム

以下の手順で解を求めます。

1. グラフの構築: 入力された \(M\) 本のトンネルのうち、直径 \(W_i\) が \(K\) 以上であるものだけを隣接リスト形式で保持します。
2. 幅優先探索 (BFS) の準備:
   • 各地点への最小トンネル数を記録する配列 dist を用意し、初期値を -1（未訪問）とします。
   • 地点 1 の距離を 0 とし、キューに 1 を追加します。
3. 探索の実行:
   • キューから現在の地点を取り出します。
   • 現在の地点から隣接している地点のうち、まだ訪問していない（dist が -1 の）地点について、距離を 現在の距離 + 1 として更新し、キューに追加します。
   • もし地点 \(N\) に到達したら、その時点の距離が最小の本数です。
4. 結果の出力:
   • 地点 \(N\) に到達できた場合はその距離を、キューが空になっても到達できなかった場合は -1 を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • グラフの構築に \(O(M)\)、BFS による探索で各頂点と各辺を最大 1 回ずつ走査するため \(O(N + M)\) となります。制約の \(N, M \leq 2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N + M)\)
  • 隣接リストの保存に \(O(N + M)\)、距離配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python の場合、入力データが多いときは sys.stdin.read().split() などを使って一括で読み込むと実行時間を短縮できます。

• キューの利用: BFS を行う際は、先頭からの取り出しが \(O(1)\) で行える collections.deque を使用するのが一般的です（リストの pop(0) は \(O(N)\) かかるため避けます）。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力をすべて読み込み、整数のリストに変換します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    data = list(map(int, input_data))

    N, M, K = data[0], data[1], data[2]

    # 中継局1から中継局Nまでの最短経路を求めるため、
    # 直径がK以上であるトンネルのみを隣接リストに追加します
    adj = [[] for _ in range(N + 1)]
    it = iter(data[3:])
    for u, v, w in zip(it, it, it):
        if w >= K:
            adj[u].append(v)
            adj[v].append(u)

    # N=1の場合は移動不要なので0を出力（制約上N>=2ですが、念のため）
    if N == 1:
        print(0)
        return

    # 幅優先探索 (BFS) により最短経路（最小トンネル数）を求めます
    # dist[i] は中継局1から中継局iまでの最小トンネル数を表します
    dist = [-1] * (N + 1)
    dist[1] = 0
    queue = deque([1])

    while queue:
        curr = queue.popleft()
        
        next_dist = dist[curr] + 1
        for neighbor in adj[curr]:
            if dist[neighbor] == -1:
                dist[neighbor] = next_dist
                # 顧客ビルのある中継局Nに到達した時点でその距離を出力して終了
                if neighbor == N:
                    print(next_dist)
                    return
                queue.append(neighbor)

    # 全ての到達可能な経路を探索しても中継局Nに辿り着けない場合
    print("-1")

if __name__ == '__main__':
    solve()

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