Overview

Given N locations with assigned altitudes and M mountain trails, the problem asks to find the minimum total fatigue to travel from location 1 to location N using only trails whose fatigue is at most K.

Analysis

This problem is a shortest path problem on a graph where each edge’s cost is defined as the absolute difference in altitude. However, there is an important constraint: “an edge can only be traversed if its cost is at most K.”

A naive approach would be to apply Dijkstra’s algorithm considering all edges, but directly applying it would include edges exceeding K. Therefore, by pre-filtering the edges and only including those with cost at most K in the graph, we can ensure that only valid paths are explored.

Algorithm

1. Graph Construction: For each mountain trail, compute the altitude difference (cost) and add it to the graph only if it is at most K.
2. Dijkstra’s Algorithm: Starting from location 1, compute the shortest path using only traversable edges.
3. Result Determination: If the distance to location N remains at its initial value (INF), the destination is unreachable; otherwise, output the computed minimum fatigue.

The reason for using Dijkstra’s algorithm is that all edge costs are non-negative (since they are absolute differences in altitude, they are always non-negative).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • \(O(M)\) for graph construction, \(O((N + M) \log N)\) for running Dijkstra’s algorithm
• Space complexity: \(O(N + M)\)
  • Memory for the graph representation and the distance array

Implementation Notes

• Use sys.stdin.read() for bulk input reading since the input data can be large

• Use a large number (\(10^{18}\)) as INF

• Efficient implementation of Dijkstra’s algorithm using a heap

• Filter edges by checking whether their cost is at most K before adding them

• Don’t forget to handle the case where the destination is unreachable

  Source Code

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

This editorial was generated by deepseekv3.