Overview

This problem asks us to find the shortest path from point \(1\) to point \(N\), using only mountain trails within a limited stamina of \(K\). The cost of each edge is determined by the absolute difference in elevation.

Analysis

This problem can be viewed as a shortest path problem on a graph. We treat each point as a vertex and each passable mountain trail as a weighted edge.

Key Observations

• Trail passability condition: the absolute difference in elevation must be at most \(K\)
• Path cost: the sum of elevation differences of the trails used
• Objective: find the shortest path (minimum cost) from point \(1\) to point \(N\)

What About a Naive Approach?

For example, breadth-first search (BFS) is good at minimizing the “number of steps,” but it cannot minimize the “sum of costs.” If we perform an exhaustive search using DFS or similar methods, the number of vertices and edges can be up to \(2 \times 10^5\), making it infeasible in terms of time (TLE).

Solution

To solve the single-source shortest path problem on a weighted graph, Dijkstra’s algorithm is effective. We simply need to include only the passable edges (elevation difference \(\leq K\)) in the graph.

Algorithm

1. Graph Construction

   • For each mountain trail, compute the elevation difference \(|H_u - H_v|\)
   • Only include edges where the difference is at most \(K\) (with the elevation difference as the cost)
   • Since the graph is undirected, add edges in both directions

2. Shortest Distance Search Using Dijkstra’s Algorithm

   • Prepare a distance array dist to record the shortest distance from vertex \(1\), initialized to \(\infty\) (except dist[1] = 0)
   • Use a priority queue (heap) to extract and explore the vertex with the current minimum cost
   • When vertex \(N\) is reached, the cost at that point is the answer
   • If vertex \(N\) is unreachable after exploring everything, output -1

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the complexity of Dijkstra’s algorithm. Each priority queue operation costs \(\log N\)
• Space complexity: \(O(N + M)\)
  • For the graph’s adjacency list and the distance array

Implementation Notes

• Use sys.stdin.read for fast input reading (important in Python)

• Store (cost, vertex) tuples in Dijkstra’s heap

• Since vertex indices are 1-indexed, set the array size to \(N+1\)

• Don’t forget to output -1 when no path exists

  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
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(data[idx]); idx += 1
    
    # グラフ構築
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        cost = abs(H[u] - H[v])
        if cost <= K:
            graph[u].append((v, cost))
            graph[v].append((u, cost))
    
    # ダイクストラ法
    dist = [float('inf')] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]  # (距離, 頂点)
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v, cost in graph[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    print(-1)

if __name__ == "__main__":
    main()

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