概要

標高が設定されたN個の地点とM本の登山道があり、疲労度がK以下の登山道のみを使って地点1から地点Nまでの最小疲労度合計を求める問題です。

考察

この問題は、各辺のコストが標高差の絶対値で定義されるグラフ上での最短経路問題です。ただし、重要な制約として「各辺のコストがK以下でなければ通れない」という条件があります。

素朴なアプローチとして全ての辺を考慮したダイクストラ法が考えられますが、そのまま適用するとKを超える辺も含まれてしまいます。そこで、事前に辺をフィルタリングして、K以下のコストの辺だけをグラフに含めることで、条件を満たす経路のみを探索できます。

アルゴリズム

1. グラフ構築: 各登山道について、その標高差（コスト）を計算し、K以下のものだけをグラフに追加します
2. ダイクストラ法: 地点1を始点として、通行可能な辺のみを使用して最短経路を計算します
3. 結果判定: 地点Nまでの距離が初期値（INF）のままなら到達不能、そうでなければ計算された最小疲労度を出力します

ダイクストラ法を使用する理由は、全ての辺のコストが非負であるためです（標高差の絶対値なので常に非負）。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • グラフ構築に\(O(M)\)、ダイクストラ法の実行に\(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)
  • グラフの表現と距離配列のためのメモリ

実装のポイント

• 入力データが大きいためsys.stdin.read()で一括読み込み

• 巨大な数値（\(10^{18}\)）をINFとして使用

• ヒープを用いたダイクストラ法の効率的な実装

• 辺を追加する前にコストがK以下かチェックしてフィルタリング

• 到達不能な場合の処理を忘れずに実装

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); K = int(next(it))
    H = [0] * (n+1)
    for i in range(1, n+1):
        H[i] = int(next(it))
        
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it))
        cost_uv = abs(H[u] - H[v])
        if cost_uv <= K:
            graph[u].append((v, cost_uv))
            graph[v].append((u, cost_uv))
            
    INF = 10**18
    dist = [INF] * (n+1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        if node == n:
            break
            
        for neighbor, cost in graph[node]:
            new_d = d + cost
            if new_d < dist[neighbor]:
                dist[neighbor] = new_d
                heapq.heappush(heap, (new_d, neighbor))
                
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。