Overview

This problem asks us to find the shortest path (minimum number of edges traversed) from point 1 to point \(N\), using only roads that satisfy the given condition (tunnel diameter is at least \(K\)).

Analysis

The key points for solving this problem are the following two:

1. Excluding edges that don’t satisfy the condition The problem states that “all tunnels on the path must have a diameter of at least \(K\).” In other words, tunnels with diameter \(W_i\) less than \(K\) cannot be used in the path at all. Therefore, by ignoring edges with \(W_i < K\) from the start when constructing the graph, we can simplify the condition.

2. Computing the shortest path The requirement to “minimize the number of tunnels traversed” corresponds to the “shortest path problem on an unweighted graph” in graph theory. Since every edge has a cost of 1 (one tunnel), we don’t need complex algorithms like Dijkstra’s — we can efficiently find the shortest distance using Breadth-First Search (BFS).

If point \(N\) cannot be reached even after the entire search is completed, it means no path exists, so we output -1.

Algorithm

We find the solution using the following steps:

1. Graph construction: Among the \(M\) input tunnels, only those with diameter \(W_i\) of at least \(K\) are stored in adjacency list format.
2. BFS preparation:
   • Prepare an array dist to record the minimum number of tunnels to each point, initialized to -1 (unvisited).
   • Set the distance of point 1 to 0 and add 1 to the queue.
3. Search execution:
   • Dequeue the current point from the queue.
   • For adjacent points that have not yet been visited (dist is -1), update the distance to current distance + 1 and add them to the queue.
   • If point \(N\) is reached, the distance at that moment is the minimum number of tunnels.
4. Output the result:
   • If point \(N\) was reached, output its distance. If the queue becomes empty without reaching it, output -1.

Complexity

• Time complexity: \(O(N + M)\)
  • Graph construction takes \(O(M)\), and the BFS traverses each vertex and each edge at most once, resulting in \(O(N + M)\). This is sufficiently fast for the constraints \(N, M \leq 2 \times 10^5\).
• Space complexity: \(O(N + M)\)
  • The adjacency list uses \(O(N + M)\) memory, and the distance array uses \(O(N)\) memory.

Implementation Notes

• Fast I/O: In Python, when there is a large amount of input data, reading it all at once using sys.stdin.read().split() can reduce execution time.

• Queue usage: When performing BFS, it is standard practice to use collections.deque, which supports \(O(1)\) removal from the front (using pop(0) on a list should be avoided as it takes \(O(N)\)).

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.