概要

直径が \(K\) 以上のトンネルだけを使って中継局 \(1\) から \(N\) へ行けるかを判定し、行けるなら通過トンネル本数（辺数）が最小の経路長を求めます。

考察

この問題の条件は「通れるトンネルは直径 \(W_i \ge K\) のものに限る」というフィルタです。
つまり、使える辺だけ残したグラフを考えれば、あとは

• 到達可能か？（連結か？）
• 到達できるなら最短の辺数はいくつか？

を求めるだけになります。

ここで「コスト＝通過トンネル本数」なので、各トンネル（辺）の重みはすべて \(1\) とみなせます。
重みがすべて同じ（等しい）グラフの最短経路は、ダイクストラではなく BFS（幅優先探索）で最短距離（最小辺数）が求まります。

素朴に「条件を満たす経路を全探索」すると、経路数は指数的に増えて現実的な時間では終わりません。
一方、BFSなら「各頂点を最初に訪れた時点が最短」と保証されるため、\(N, M \le 2\times 10^5\) でも間に合います。

アルゴリズム

1. 隣接リスト adj を用意する。
2. 入力された各トンネル \((u, v, w)\) について、\(w \ge K\) のときだけ adj[u] と adj[v] に互いを追加する
   （直径が足りないトンネルは最初から“存在しない”ものとして無視する）。
3. BFS を行い、dist[x] = 1 から x までの最小辺数 を求める。
   • 初期状態：dist[1] = 0、それ以外は -1（未訪問）
   • キューから取り出した頂点 x の隣 y が未訪問なら dist[y] = dist[x] + 1 としてキューへ入れる
4. BFS 終了後、dist[N] がそのまま答え：
   • 到達できれば最小トンネル本数
   • 到達できなければ -1

例えば「直径条件で辺を間引いた結果、1 と N が別の連結成分になった」なら BFS でも N に到達できず、-1 になります。

計算量

• 時間計算量: \(O(N + M)\)
  （辺のフィルタ付きで隣接リストを作り、BFS で各頂点・各辺を高々1回ずつ処理）
• 空間計算量: \(O(N + M)\)
  （隣接リストと距離配列、キュー）

実装のポイント

• 最初に \(w \ge K\) の辺だけを隣接リストに入れると、BFS 中に毎回条件判定する必要がなくなり実装が簡潔になります。

• dist を -1 初期化にすると、「未訪問判定」と「到達不可の場合の出力」を同時に扱えて便利です。

• 入力サイズが大きいので、sys.stdin.buffer.read() で高速に読み込む実装にしています。

  ソースコード

import sys
from collections import deque

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        N = next(it)
    except StopIteration:
        return
    M = next(it)
    K = next(it)

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it); w = next(it)
        if w >= K:
            adj[u].append(v)
            adj[v].append(u)

    dist = [-1] * (N + 1)
    dq = deque([1])
    dist[1] = 0
    while dq:
        x = dq.popleft()
        if x == N:
            break
        nx = dist[x] + 1
        for y in adj[x]:
            if dist[y] == -1:
                dist[y] = nx
                dq.append(y)

    print(dist[N])

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。