概要

この問題は、与えられた \(N\) 個の地点と \(M\) 本の登山道からなるグラフにおいて、各辺の重み（標高差）が \(K\) 以下という条件を満たしつつ、地点 1 から地点 \(N\) までの最短経路（標高差の合計の最小値）を求める問題です。

考察

この問題のポイントは、以下の 2 点を整理することです。

1. 通行不可能な道の除外: 「標高差が \(K\) を超える登山道は通れない」という制約があります。これは、グラフを構築する際に、条件 \(|H_{U_j} - H_{V_j}| \le K\) を満たさない辺を最初から無視（削除）して考えればよいことを意味します。
2. 最短経路の算出: 通行可能な道だけを考えたとき、経路上の標高差の合計を最小化したいという要求は、グラフ理論における「単一始点最短経路問題」そのものです。

標高差の絶対値は常に 0 以上の値（非負）であるため、負の辺が存在しないグラフにおける最短経路アルゴリズムである ダイクストラ法 を適用するのが最適です。

もし、標高差の制約（\(K\)）を考慮せずにダイクストラ法を適用してしまうと、本来通れない道を通った結果が答えになってしまうため、必ず辺の選別を先に行う必要があります。

アルゴリズム

以下の手順で解を求めます。

1. グラフの構築: 各登山道 \((U_j, V_j)\) について、標高差 \(w = |H_{U_j} - H_{V_j}|\) を計算します。 \(w \le K\) であれば、隣接リストに重み \(w\) の無向辺を追加します。\(w > K\) であれば、その辺は破棄します。
2. ダイクストラ法の実行:
   • 始点（地点 1）からの暫定距離を保持する配列 dist を無限大で初期化し、dist[1] = 0 とします。
   • 優先度付きキュー（ヒープ）に (距離 0, 地点 1) を追加します。
   • キューが空になるまで、以下の操作を繰り返します。
     1. キューから最も距離が小さい地点 \(u\) を取り出す。
     2. すでにより短い距離で確定している場合はスキップする。
     3. 地点 \(u\) に隣接する各地点 \(v\) について、現在の距離に辺の重みを加えた値が dist[v] より小さければ、dist[v] を更新してキューに \((dist[v], v)\) を追加する。
3. 結果の出力: dist[N] が無限大のままであれば到達不可能なので -1 を出力し、そうでなければ dist[N] の値を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  • グラフの構築に \(O(M)\)、ダイクストラ法において各辺を最大 1 回ずつ探索し、優先度付きキューの操作に \(\log N\) かかるため、全体で \(O(M \log N)\) となります。今回の制約（\(N, M \le 2 \times 10^5\)）では十分に高速です。
• 空間計算量: \(O(N + M)\)
  • 隣接リストおよび距離配列を保持するために、頂点数と辺の数に比例したメモリが必要です。

実装のポイント

• 高速な入出力: Python の場合、input() を繰り返すと時間がかかることがあるため、sys.stdin.read().split() などで一括で読み込むと効率的です。

• 0-indexed への変換: プログラム上では地点 1〜\(N\) を 0〜\(N-1\) として扱うと、配列のインデックス操作がスムーズになります。

• 優先度付きキュー: Python の heapq モジュールは最小ヒープを提供しているため、最短経路問題にそのまま利用できます。キューに入れる要素は (コスト, 地点) の順にすることで、コストが最小のものが優先的に取り出されます。

  ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。