Overview

This problem asks us to find a path from point \(1\) to point \(N\) that minimizes the “total elevation difference (fatigue)” under the constraint that only mountain trails with an elevation difference of \(K\) or less can be used.

Analysis

• The fatigue of each mountain trail is \(|H_u - H_v|\), with the additional constraint that “a trail cannot be used if its fatigue exceeds \(K\).”
  In other words, we only need to consider a graph where usable edges (trails) are limited to those with \(|H_u - H_v| \le K\).
• On this graph, we want to minimize the total fatigue along the path (the sum of edge weights), so this is exactly a shortest path problem on a weighted graph (with non-negative edge weights).
• Naively “exhaustively searching all reachable paths (trying all paths via DFS/BFS)” would cause an explosion in the number of paths and is practically infeasible.
• Also, BFS finds the path with the minimum “number of edges,” but what we want to minimize here is the “sum of weights,” so it is inappropriate (since the weights are not uniform).
• Since all edge weights are non-negative and \(N, M \le 2 \times 10^5\) is large, Dijkstra’s algorithm is the standard appropriate choice.

Algorithm

1. Build a graph from the input. For each edge \((u, v)\), compute the weight \(w = |H_u - H_v|\).
2. If \(w \le K\), the edge is passable, so add it to the adjacency list. Edges with \(w > K\) are ignored from the start (since they cannot be traversed).
3. On the graph consisting only of passable edges, compute the shortest distance from source \(1\) (or 0 in 0-indexed) using Dijkstra’s algorithm.
   • Let dist[i] be “the minimum total fatigue from point \(1\) to point \(i\).”
   • Using a priority queue (heap), we finalize vertices starting from the one with the currently smallest distance.
4. If dist[N] (or dist[N-1] in 0-indexed) was never updated, the destination is unreachable, so output -1. Otherwise, output that value.

Example: If the elevations are \([0, 5, 9]\), edges are \((1,2),(2,3)\), and \(K=4\), then
the weight of \((1,2)\) is \(5\) so it cannot be traversed, and the weight of \((2,3)\) is \(4\) so it can be traversed, but since we cannot get from 1 to 2 in the first place, the destination is unreachable and the answer is -1.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Standard complexity of Dijkstra’s algorithm implemented with an adjacency list + heap. The edge filtering itself is \(O(M)\).)
• Space complexity: \(O(N+M)\)
  (Adjacency list, distance array, heap, etc.)

Implementation Notes

• Edges that cannot be traversed (\(|H_u-H_v|>K\)) should not be added to the graph from the start, which eliminates unnecessary exploration during Dijkstra’s algorithm.

• In Dijkstra’s algorithm, the state (d, x) popped from the heap may contain outdated information, so the check if d != dist[x]: continue is important.

• Set INF to a sufficiently large value (e.g., \(10^{30}\)) and use it for reachability checks.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)
    H = [next(it) for _ in range(N)]

    g = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = H[u] - H[v]
        if w < 0:
            w = -w
        if w <= K:
            g[u].append((v, w))
            g[v].append((u, w))

    INF = 10**30
    dist = [INF] * N
    dist[0] = 0
    pq = [(0, 0)]

    while pq:
        d, x = heapq.heappop(pq)
        if d != dist[x]:
            continue
        if x == N - 1:
            break
        for y, w in g[x]:
            nd = d + w
            if nd < dist[y]:
                dist[y] = nd
                heapq.heappush(pq, (nd, y))

    ans = dist[N - 1]
    if ans >= INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.