Overview

This problem asks us to determine whether we can reach relay station \(N\) from relay station \(1\) using only tunnels with diameter \(K\) or greater, and if reachable, to find the minimum number of tunnels (shortest path length).

Analysis

Key Insight

This problem has the constraint of “paths where all tunnels have diameter at least \(K\).” In other words, tunnels with diameter less than \(K\) simply cannot be used.

Therefore, if we consider a new graph that keeps only the tunnels with diameter \(K\) or greater out of the \(M\) tunnels, the problem reduces to a simple shortest path problem.

Comparison with a Naive Approach

If we take the approach of “enumerating all paths and checking whether they satisfy the condition,” the number of paths grows exponentially, making it completely infeasible. However, if we construct a graph using only the usable tunnels, it becomes a shortest path problem where all edge weights are 1 (1 tunnel = cost 1).

When all edge weights are equal, the shortest path problem can be solved in \(O(N + M)\) using BFS (Breadth-First Search). There is no need to use Dijkstra’s algorithm.

Algorithm

1. Graph Construction: For each tunnel, add it as an edge to the adjacency list only if its diameter \(W_i \geq K\).
2. BFS (Breadth-First Search): Perform BFS starting from relay station \(1\) to find the shortest distance (number of tunnels traversed) to each vertex.
3. Output the Result: If relay station \(N\) is reachable, output the distance; otherwise, output \(-1\).

Concrete Example

For instance, suppose \(N = 4, K = 5\) with the following tunnels:

• \(1 \leftrightarrow 2\) (diameter \(10\)) → \(10 \geq 5\), so usable
• \(2 \leftrightarrow 4\) (diameter \(3\)) → \(3 < 5\), so not usable
• \(1 \leftrightarrow 3\) (diameter \(7\)) → \(7 \geq 5\), so usable
• \(3 \leftrightarrow 4\) (diameter \(6\)) → \(6 \geq 5\), so usable

Running BFS on the graph with only usable tunnels, we find the path \(1 \to 3 \to 4\), and the answer is \(2\).

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for graph construction, \(O(N + M)\) for BFS
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency list, \(O(N)\) for the distance array

Implementation Notes

• Perform filtering during graph construction: Rather than checking \(W_i \geq K\) every time during BFS traversal, adding only edges that satisfy the condition at the graph construction stage makes the code simpler.

• Terminate immediately when vertex \(N\) is reached during BFS: Since BFS explores vertices in order of increasing distance from the source, the first time vertex \(N\) is reached, that is the shortest distance. Early termination avoids unnecessary exploration.

• Use sys.stdin.readline: In Python, the standard input() is slow when there is a large amount of input, so using sys.stdin.readline provides a speedup.

• Use deque: Use collections.deque for the BFS queue. A list’s pop(0) is \(O(N)\), but deque’s popleft() operates in \(O(1)\).

  Source Code

from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        if w >= K:
            graph[u].append(v)
            graph[v].append(u)
    
    # BFS from node 1 to node N
    dist = [-1] * (N + 1)
    dist[1] = 0
    queue = deque([1])
    while queue:
        node = queue.popleft()
        if node == N:
            print(dist[N])
            return
        for nxt in graph[node]:
            if dist[nxt] == -1:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    
    print(-1)

main()

---

This editorial was generated by claude4.6opus-thinking.