Overview

This problem asks us to find the shortest path (minimum total elevation difference) from point 1 to point \(N\) in a graph consisting of \(N\) given points and \(M\) mountain trails, under the condition that the weight (elevation difference) of each edge is at most \(K\).

Analysis

The key to this problem is organizing the following two points:

1. Excluding impassable trails: There is a constraint that “trails with an elevation difference exceeding \(K\) cannot be traversed.” This means that when constructing the graph, we can simply ignore (remove) from the start any edges that do not satisfy the condition \(|H_{U_j} - H_{V_j}| \le K\).
2. Computing the shortest path: When considering only passable trails, the requirement to minimize the total elevation difference along a path is exactly the “single-source shortest path problem” in graph theory.

Since the absolute value of the elevation difference is always non-negative (≥ 0), it is optimal to apply Dijkstra’s algorithm, which is a shortest path algorithm for graphs with no negative edges.

If we apply Dijkstra’s algorithm without considering the elevation constraint (\(K\)), the result might include paths through trails that are actually impassable, so we must filter the edges first.

Algorithm

We find the solution using the following steps:

1. Graph Construction: For each mountain trail \((U_j, V_j)\), compute the elevation difference \(w = |H_{U_j} - H_{V_j}|\). If \(w \le K\), add an undirected edge with weight \(w\) to the adjacency list. If \(w > K\), discard that edge.
2. Running Dijkstra’s Algorithm:
   • Initialize an array dist that holds tentative distances from the source (point 1) to infinity, and set dist[1] = 0.
   • Add (distance 0, point 1) to a priority queue (heap).
   • Repeat the following operations until the queue is empty:

        1. Extract the point $u$ with the smallest distance from the queue.
        2. If a shorter distance has already been finalized, skip it.
        3. For each point $v$ adjacent to point $u$, if the current distance plus the edge weight is less than `dist[v]`, update `dist[v]` and add $(dist[v], v)$ to the queue.
     

3. Output the Result: If dist[N] remains infinity, the destination is unreachable, so output -1. Otherwise, output the value of dist[N].

Complexity

• Time Complexity: \(O(M \log N)\)
  • Graph construction takes \(O(M)\), and in Dijkstra’s algorithm each edge is explored at most once with priority queue operations costing \(\log N\), giving an overall complexity of \(O(M \log N)\). This is sufficiently fast for the given constraints (\(N, M \le 2 \times 10^5\)).
• Space Complexity: \(O(N + M)\)
  • Memory proportional to the number of vertices and edges is needed to store the adjacency list and the distance array.

Implementation Notes

• Fast I/O: In Python, repeatedly calling input() can be slow, so it is more efficient to read all input at once using sys.stdin.read().split() or similar methods.

• Conversion to 0-indexed: In the program, handling points 1 through \(N\) as 0 through \(N-1\) makes array index operations smoother.

• Priority Queue: Python’s heapq module provides a min-heap, which can be used directly for shortest path problems. By inserting elements into the queue in the order (cost, point), the element with the minimum cost is extracted first.

  Source Code

import sys
import heapq

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする（高速な入出力のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 地点の数, M: 登山道の数, K: 体力（許容される標高差）
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 各地点の標高をリストに格納
    H = [int(x) for x in input_data[3:3+N]]
    
    # 隣接リストを作成
    adj = [[] for _ in range(N)]
    ptr = 3 + N
    for _ in range(M):
        # 登山道の情報を取得（1-indexedを0-indexedに変換）
        u = int(input_data[ptr]) - 1
        v = int(input_data[ptr+1]) - 1
        ptr += 2
        
        # 標高差を計算し、K以下であれば通行可能としてグラフに追加
        diff = abs(H[u] - H[v])
        if diff <= K:
            adj[u].append((v, diff))
            adj[v].append((u, diff))
            
    # ダイクストラ法による最短経路探索
    # dist[i] は地点1（インデックス0）から地点iまでの最小疲労度合計
    dist = [float('inf')] * N
    dist[0] = 0
    
    # 優先度付きキュー (現在の疲労度合計, 現在の地点)
    pq = [(0, 0)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに確定している最短距離より長い場合はスキップ
        if d > dist[u]:
            continue
        
        # 目的地（地点N、インデックスN-1）に到達した場合、その時点のdが最小値
        if u == N - 1:
            print(d)
            return
            
        # 隣接する地点を探索
        for v, weight in adj[u]:
            new_dist = d + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    # 目的地まで到達できなかった場合
    print("-1")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.