Overview

This is a problem of finding the path from relay station 1 to relay station N where all tunnel diameters are at least K, and among such paths, the number of tunnels traversed is minimized.

Analysis

This problem asks us to find the shortest path (in terms of number of edges) from vertex 1 to vertex N, using only edges whose weight (diameter) is at least K. The weight of each edge is not used as an actual distance but only for condition checking.

A straightforward approach is BFS (Breadth-First Search) that examines all edges. However, unlike standard BFS which ignores edge weights, in this problem we need to only traverse edges that satisfy the condition “diameter is at least K.”

The key observation is that edges with weight less than K cannot be traversed, so they can be excluded from the graph. In other words, we only need to find the shortest path from vertex 1 to vertex N on the subgraph containing only edges with diameter at least K.

Algorithm

1. Build a graph from the input. For each vertex, maintain a list of (connected vertex, tunnel diameter) pairs.
2. Use Breadth-First Search (BFS) to find the shortest path (number of tunnels traversed) from vertex 1.
3. During BFS exploration, for each edge connected to the current vertex, check whether the diameter is at least K.
4. Only traverse edges with diameter at least K. If an unvisited vertex or a vertex reachable via a shorter path is found, update the distance and add it to the queue.
5. Finally, if the distance to vertex N has been determined, output it; otherwise, output -1 if it is unreachable.

Complexity

• Time complexity: \(O(N + M)\)
  • Because each vertex and each edge is processed at most once
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the graph representation, \(O(N)\) for the distance array, and \(O(N)\) for the queue

Implementation Notes

• Represent the graph as an adjacency list, storing (destination, diameter) information for each edge

• Use a queue (deque) for BFS, processing in first-in-first-out order

• Initialize the distance array to infinity (INF), and set the distance from vertex 1 to 0

• Always check that the diameter is at least K before traversing an edge, and only traverse edges that satisfy the condition

• Update the distance and add to the queue only when a shorter path is found

  Source Code

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

This editorial was generated by deepseekv3.