概要

この問題は、与えられたグラフにおいて、辺の重みが \(K\) 以上であるような辺のみを使って頂点 \(1\) から頂点 \(N\) へのパスが存在するかを判定し、存在すればその経路における辺の本数（ホップ数）の最小値を求めるものです。

考察

この問題は、グラフ上の最短経路問題に帰着できます。

重要な観察

• 各トンネルには「直径」が定義されており、それがケーブルの太さ \(K\) 以上でないと利用できません。
• 従って、直径が \(K\) 未満のトンネルは経路として選んでも意味がないため、無視して考えることができます。
• この条件を満たすトンネル（辺）のみを用いて構成されるグラフを考えると、これは重みなしグラフとみなせます。
• 頂点 \(1\) から頂点 \(N\) への経路のうち、通る辺の数が最小のものを求めたいので、これは典型的な幅優先探索（BFS）によって解くことができます。

素朴なアプローチの問題点

もしダイクストラ法のような重み付き最短経路アルゴリズムを使ってしまうと、計算量が大きくなりすぎたり、実装が複雑になります。しかし、今回は「辺の本数の最小化」であり、「距離の和の最小化」ではないため、重みを考慮せず単純な BFS で十分です。

解決方法

• 直径が \(K\) 以上の辺のみを使って隣接リスト形式のグラフを構築します。
• その後、頂点 \(1\)（0-indexed では 0）から頂点 \(N\)（N-1）への最短経路（辺数）を BFS により求めます。
• BFS は各辺の重みがすべて \(1\) であると仮定したときの最短経路を正確に求めることができるため、非常に効率的です。

アルゴリズム

1. 入力の読み込み

   • 頂点数 \(N\)、辺数 \(M\)、ケーブルの太さ \(K\) を読み込む。
   • 各辺について、直径 \(W_i\) が \(K\) 以上であれば、隣接リストに追加する（無向グラフなので両方向）。

2. BFSによる最短経路探索

   • 頂点 \(0\) からの距離を管理する配列 dist を用意し、初期値を -1 とする。
   • 頂点 \(0\) の距離を 0 とし、キューに追加する。
   • キューが空になるまで以下を繰り返す：
     • キューの先頭要素を取り出し、その隣接頂点に対して距離が未確定であれば更新し、キューに追加する。

3. 結果の出力

   • 頂点 \(N-1\) の距離が -1 なら到達不可能なので -1 を出力。
   • そうでなければ、その距離を出力。

計算量

• 時間計算量: \(O(N + M)\)
  • グラフの構築に \(O(M)\)、BFSに \(O(N + M)\)。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列、キューのサイズ合わせて \(O(N + M)\)。

実装のポイント

• グラフは0-indexedで扱っているため、入力の頂点番号は1引く必要がある。
• BFSは通常queueモジュールを使うことが多いが、高速化のためにリストを使ったシミュレーションも有効（先頭インデックスを管理する方式）。
• 入力を高速に読み込むために sys.stdin.read() を使用している。

## ソースコード

```python
import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    # グラフ構築: 辺は直径がK以上のもののみ使用可能
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1
        idx += 1
        v = int(data[idx]) - 1
        idx += 1
        w = int(data[idx])
        idx += 1
        if w >= K:
            graph[u].append(v)
            graph[v].append(u)
    
    # 0-indexed でノード 0 から N-1 への最短経路 (BFS)
    dist = [-1] * N
    queue = [0]
    dist[0] = 0
    front = 0
    while front < len(queue):
        u = queue[front]
        front += 1
        d = dist[u]
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = d + 1
                queue.append(v)
    
    print(dist[N-1])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。