概要

標高差が体力 \(K\) を超える登山道を除外した上で、地点 \(1\) から地点 \(N\) への最短経路（疲労度の合計が最小）を求める問題です。典型的な条件付き最短経路問題であり、ダイクストラ法で解けます。

考察

重要な気づき

1. 使えない辺がある: 登山道の標高差 \(|H_{U_j} - H_{V_j}|\) が \(K\) を超える場合、その登山道はそもそも通れません。つまり、グラフからその辺を取り除いて考えてよいです。

2. 辺の重みは非負: 疲労度は標高差の絶対値なので、必ず \(0\) 以上です。これは非常に重要で、辺の重みが非負であればダイクストラ法が使えることを意味します。

3. 最短経路問題に帰着: 通行可能な辺だけで構成されたグラフにおいて、地点 \(1\) から地点 \(N\) への最短距離を求める問題と同じです。

素朴なアプローチとの比較

• BFS（幅優先探索）: 辺の重みがすべて同じ（重みなし）なら BFS で十分ですが、今回は辺ごとに重みが異なるため BFS では最短距離を正しく求められません。
• ベルマン・フォード法: 正しく求められますが、計算量が \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合は遅すぎます。
• ダイクストラ法: 辺の重みが非負なので適用可能で、優先度付きキューを使えば \(O((N + M) \log N)\) で効率的に解けます。

アルゴリズム

1. グラフの構築: 各登山道について標高差 \(|H_{U_j} - H_{V_j}|\) を計算し、\(K\) 以下であれば隣接リストに追加します。\(K\) を超える辺は無視します。

2. ダイクストラ法の実行:

   • 地点 \(1\) の距離を \(0\)、それ以外を \(\infty\) で初期化します。
   • 優先度付きキュー（最小ヒープ）に \((0, 1)\)（距離, 地点）を入れます。
   • キューから最小距離の地点を取り出し、隣接する地点への距離を更新（緩和）します。
   • 地点 \(N\) を取り出した時点で、その距離が答えです。

3. 到達不能の判定: キューが空になっても地点 \(N\) に到達できなかった場合、-1 を出力します。

具体例

例えば、\(N=3, M=2, K=5\)、標高が \(H = [10, 13, 20]\)、辺が \((1,2)\) と \((2,3)\) の場合： - 辺 \((1,2)\): 標高差 \(|10-13| = 3 \leq 5\) → 通行可能、疲労度 \(3\) - 辺 \((2,3)\): 標高差 \(|13-20| = 7 > 5\) → 通行不可

辺 \((2,3)\) が使えないため、地点 \(1\) から地点 \(3\) に到達できず、答えは -1 です。

計算量

• 時間計算量: \(O((N + M) \log N)\)（ダイクストラ法の標準的な計算量）
• 空間計算量: \(O(N + M)\)（隣接リストと距離配列の格納）

実装のポイント

• 辺のフィルタリングをグラフ構築時に行う: 隣接リストに追加する段階で \(K\) を超える辺を除外することで、ダイクストラ法の探索中に毎回判定する必要がなくなり、コードが簡潔になります。

• 早期終了: 地点 \(N\) がキューから取り出された時点で最短距離が確定するため、即座に答えを出力して終了できます。これにより不要な探索を省けます。

• 高速入力: sys.stdin.buffer.read() を使ってまとめて読み込むことで、Python でも入力がボトルネックになりにくくなります。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        diff = abs(H[u] - H[v])
        if diff <= K:
            adj[u].append((v, diff))
            adj[v].append((u, diff))
    
    # Dijkstra from node 1 to node N
    INF = float('inf')
    dist = [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, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(-1)

main()

この解説は claude4.6opus-thinking によって生成されました。