概要

中継局1から中継局Nまでの経路で、すべてのトンネルの直径がK以上のものの中で、通過するトンネルの本数が最小のものを求める問題です。

考察

この問題は、辺の重み（直径）がK以上という条件を満たす辺のみを使って、頂点1から頂点Nへの最短経路（辺の本数）を求める問題です。各辺の重みは実際の距離ではなく、条件チェックにのみ使用されます。

素朴なアプローチとして、すべての辺を調べるBFS（幅優先探索）が考えられます。ただし、通常のBFSでは辺の重みを無視してしまいますが、この問題では「直径がK以上」という条件を満たす辺だけを通る必要があります。

重要な観察は、辺の重みがK未満の辺は通れないため、グラフから除外できるということです。つまり、直径がK以上の辺だけを含む部分グラフ上で、頂点1から頂点Nへの最短経路を求めればよいのです。

アルゴリズム

1. 入力からグラフを構築します。各頂点からは（接続先頂点, トンネル直径）のリストを保持します。
2. 幅優先探索（BFS）を使用して、頂点1からの最短経路（通過するトンネルの本数）を求めます。
3. BFSの探索中に、現在の頂点から接続されている各辺について、直径がK以上かどうかをチェックします。
4. 直径がK以上の辺のみを通り、未訪問の頂点またはより短い経路で到達できる頂点を見つけた場合、距離を更新してキューに追加します。
5. 最終的に頂点Nまでの距離が求まればそれを出力し、到達不能な場合は-1を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 各頂点と各辺を高々1回ずつ処理するため
• 空間計算量: \(O(N + M)\)
  • グラフの表現に \(O(N + M)\)、距離配列に \(O(N)\)、キューに \(O(N)\) が必要

実装のポイント

• グラフを隣接リストで表現し、各辺に（接続先, 直径）の情報を保持します

• BFSではキュー（deque）を使用し、先入れ先出しで処理します

• 距離配列は初期値を無限大（INF）に設定し、頂点1からの距離を0で初期化します

• 辺を通る前に必ず直径がK以上かチェックし、条件を満たすものだけを通ります

• より短い経路が見つかった場合のみ距離を更新してキューに追加します

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); K = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    INF = float('inf')
    dist = [INF] * (n+1)
    dist[1] = 0
    queue = deque([1])
    
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            if w >= K:
                if dist[v] > dist[u] + 1:
                    dist[v] = dist[u] + 1
                    queue.append(v)
    
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。