Overview

Determine whether it is possible to travel from relay station \(1\) to \(N\) using only tunnels with diameter \(K\) or greater, and if so, find the minimum number of tunnels (edges) traversed along the path.

Analysis

The condition in this problem acts as a filter: “only tunnels with diameter \(W_i \ge K\) can be used.” In other words, if we consider the graph with only usable edges remaining, all we need to find is:

• Is the destination reachable? (Is it connected?)
• If reachable, what is the minimum number of edges?

Since “cost = number of tunnels traversed,” the weight of each tunnel (edge) can be treated as \(1\). For a graph where all weights are the same (equal), the shortest path can be found not with Dijkstra’s algorithm but with BFS (Breadth-First Search) to obtain the shortest distance (minimum number of edges).

A naive approach of “exhaustively searching all paths satisfying the condition” would result in an exponential number of paths and would not finish in a realistic amount of time. On the other hand, BFS guarantees that “the first time a vertex is visited is the shortest,” so it runs efficiently even for \(N, M \le 2\times 10^5\).

Algorithm

1. Prepare an adjacency list adj.
2. For each input tunnel \((u, v, w)\), add each to the other’s adjacency list in adj[u] and adj[v] only when \(w \ge K\) (tunnels with insufficient diameter are simply ignored as if they “don’t exist” from the start).
3. Perform BFS to compute dist[x] = minimum number of edges from 1 to x.
   • Initial state: dist[1] = 0, all others are -1 (unvisited)
   • For each vertex x dequeued, if its neighbor y is unvisited, set dist[y] = dist[x] + 1 and enqueue it
4. After BFS completes, dist[N] is directly the answer:
   • If reachable, it is the minimum number of tunnels
   • If unreachable, it is -1

For example, if “filtering edges by the diameter condition causes \(1\) and \(N\) to end up in different connected components,” then BFS also cannot reach \(N\), resulting in -1.

Complexity

• Time complexity: \(O(N + M)\) (Build the adjacency list with edge filtering, then BFS processes each vertex and each edge at most once)
• Space complexity: \(O(N + M)\) (Adjacency list, distance array, and queue)

Implementation Notes

• Adding only edges with \(w \ge K\) to the adjacency list from the start eliminates the need to check the condition during BFS, making the implementation concise.

• Initializing dist to -1 conveniently handles both “unvisited checking” and “output for the unreachable case” simultaneously.

• Since the input size can be large, the implementation uses sys.stdin.buffer.read() for fast input reading.

  Source Code

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

This editorial was generated by gpt-5.2-high.