概要

標高差が \(K\) 以下の登山道だけを使えるという制約のもとで、地点 \(1\) から地点 \(N\) までの「標高差（疲労度）の合計」が最小となる経路を求める問題です。

考察

• 各登山道の疲労度は \(|H_u - H_v|\) で、さらに「一度に通る登山道の疲労度が \(K\) を超えると通れない」という制約があります。
  つまり 使える辺（登山道）を \(|H_u - H_v| \le K\) のものに限定したグラフを考えればよいです。
• その上で、経路全体の疲労度合計（辺重みの和）を最小化したいので、これは 重み付きグラフの最短路問題そのものです（辺重みは非負）。
• 素朴に「到達可能な経路を全探索（DFS/BFSで全経路を試す）」すると、経路数が爆発して現実的に不可能です。
• また、BFS は「辺の本数」が最小の経路は求められますが、今回最小化したいのは「重みの和」なので不適切です（重みが一様ではない）。
• 辺重みがすべて非負で、\(N, M \le 2 \times 10^5\) と大きいので、標準的に ダイクストラ法が適しています。

アルゴリズム

1. 入力からグラフを作る。各辺 \((u, v)\) について重み \(w = |H_u - H_v|\) を計算する。
2. もし \(w \le K\) ならその辺は通行可能なので、隣接リストに追加する。\(w > K\) の辺は最初から無視する（通れないため）。
3. 通行可能な辺だけで構成されたグラフ上で、始点 \(1\)（0-index では 0）からの最短距離を ダイクストラ法で計算する。
   • dist[i] を「地点 \(1\) から地点 \(i\) までの疲労度合計の最小値」とする。
   • 優先度付きキュー（ヒープ）で、現在最も距離が小さい頂点から確定していく。
4. dist[N]（0-index では dist[N-1]）が更新されなかった場合、到達不能なので -1 を出力する。そうでなければその値を出力する。

例：標高が \([0, 5, 9]\)、辺が \((1,2),(2,3)\) で \(K=4\) のとき、
\((1,2)\) の重みは \(5\) で通れず、\((2,3)\) の重みは \(4\) で通れるが、そもそも 1 から 2 に行けないので到達不能となり -1 になります。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （ダイクストラ法を隣接リスト＋ヒープで実装した標準の計算量。辺のフィルタリング自体は \(O(M)\)）
• 空間計算量: \(O(N+M)\)
  （隣接リスト、距離配列、ヒープなど）

実装のポイント

• 通れない辺（\(|H_u-H_v|>K\)）は最初からグラフに入れないことで、ダイクストラ中の無駄な探索を減らせます。

• ダイクストラでは、ヒープから取り出した状態 (d, x) が古い情報の場合があるため、if d != dist[x]: continue のチェックが重要です。

• INF は十分大きい値（例：\(10^{30}\)）にして、到達判定に使います。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。