概要

この問題は、制限された体力 \(K\) 以内の登山道のみを使って、地点 \(1\) から地点 \(N\) へ移動する最短経路を求めるものです。各辺のコストは標高差の絶対値で決まります。

考察

この問題はグラフ上の最短経路問題として捉えることができます。各地点を頂点、通行可能な登山道をコスト付きの辺とみなします。

重要な観察

• 登山道の通行条件：標高差の絶対値が \(K\) 以下であること
• 経路のコスト：使用した登山道の標高差の総和
• 目的：地点 \(1\) から地点 \(N\) までの最短経路（コスト最小）

素朴な方法では？

例えば、幅優先探索（BFS）では「歩数」を最小にするのは得意ですが、「コストの和」を最小化することはできません。DFSなどで全探索すると、頂点数・辺数が最大 \(2 \times 10^5\) あるため、時間的に無理があります（TLE）。

解決策

重み付きグラフにおける単一始点最短経路問題を解くには、ダイクストラ法（Dijkstra’s algorithm）が有効です。ただし、通行可能な辺（標高差 \(\leq K\)）のみをグラフに含めればよいです。

アルゴリズム

1. グラフの構築

   • 各登山道について、標高差 \(|H_u - H_v|\) を計算
   • それが \(K\) 以下のものだけを辺として採用（コストは標高差）
   • 無向グラフなので、両方向に辺を張る

2. ダイクストラ法による最短距離探索

   • 頂点 \(1\) からの最短距離を記録する配列 dist を用意し、初期値は \(\infty\)（ただし dist[1] = 0）
   • 優先度付きキュー（ヒープ）を使って、現在の最小コストを持つ頂点を取り出して探索
   • 頂点 \(N\) に到達したらその時点のコストが答え
   • 全て探索しても到達できなければ -1 を出力

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の計算量。優先度付きキューの操作が \(\log N\) かかる
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列の分

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用（Pythonでは重要）
• ダイクストラ法のヒープには (コスト, 頂点) のタプルを入れる
• 頂点番号は1-indexedなので、配列サイズは \(N+1\) にしておく
• 経路が存在しない場合は -1 を出力することを忘れずに

## ソースコード

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

この解説は qwen3-coder-480b によって生成されました。