Overview

This problem asks us to determine whether there exists a path from vertex \(1\) to vertex \(N\) using only edges whose weight is at least \(K\) in a given graph, and if such a path exists, to find the minimum number of edges (hops) along that path.

Analysis

This problem can be reduced to a shortest path problem on a graph.

Key Observations

• Each tunnel has a defined “diameter,” and it can only be used if the diameter is at least the cable thickness \(K\).
• Therefore, tunnels with diameter less than \(K\) are useless as part of a path and can be ignored.
• If we consider the graph constructed using only tunnels (edges) that satisfy this condition, it can be treated as an unweighted graph.
• Since we want to find the path from vertex \(1\) to vertex \(N\) that minimizes the number of edges traversed, this can be solved using a typical Breadth-First Search (BFS).

Issues with a Naive Approach

If we were to use a weighted shortest path algorithm like Dijkstra’s algorithm, the computation could become too expensive or the implementation overly complex. However, since we are minimizing the number of edges rather than the sum of distances, a simple BFS without considering weights is sufficient.

Solution Method

• Build a graph in adjacency list format using only edges with diameter at least \(K\).
• Then, find the shortest path (in terms of number of edges) from vertex \(1\) (index 0 in 0-indexed) to vertex \(N\) (index N-1) using BFS.
• BFS can exactly compute the shortest path when all edge weights are assumed to be \(1\), making it very efficient.

Algorithm

1. Read Input

   • Read the number of vertices \(N\), the number of edges \(M\), and the cable thickness \(K\).
   • For each edge, if the diameter \(W_i\) is at least \(K\), add it to the adjacency list (both directions, since the graph is undirected).

2. Shortest Path Search via BFS

   • Prepare a distance array dist to manage distances from vertex \(0\), initialized to -1.
   • Set the distance of vertex \(0\) to 0 and add it to the queue.
   • Repeat the following until the queue is empty:
     • Dequeue the front element, and for each adjacent vertex whose distance has not yet been determined, update its distance and add it to the queue.

3. Output the Result

   • If the distance of vertex \(N-1\) is -1, the destination is unreachable, so output -1.
   • Otherwise, output that distance.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for graph construction, \(O(N + M)\) for BFS.
• Space complexity: \(O(N + M)\)
  • The adjacency list, distance array, and queue together use \(O(N + M)\).

Implementation Notes

• Since the graph is handled in 0-indexed format, vertex numbers from the input need to be decremented by 1.

• BFS is often implemented using the queue module, but for optimization, simulating with a list (managing a head index) is also effective.

• sys.stdin.read() is used to read input efficiently.

  Source Code

import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    # グラフ構築: 辺は直径がK以上のもののみ使用可能
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1
        idx += 1
        v = int(data[idx]) - 1
        idx += 1
        w = int(data[idx])
        idx += 1
        if w >= K:
            graph[u].append(v)
            graph[v].append(u)
    
    # 0-indexed でノード 0 から N-1 への最短経路 (BFS)
    dist = [-1] * N
    queue = [0]
    dist[0] = 0
    front = 0
    while front < len(queue):
        u = queue[front]
        front += 1
        d = dist[u]
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = d + 1
                queue.append(v)
    
    print(dist[N-1])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.