A park has waypoints 0 .. n-1; waypoint v sits at altitude height[v]. trails lists two-way trails (a, b) between waypoints. A tired hiker only cares about climbs: walking a trail to a strictly higher waypoint costs 1 climb, while walking to an equal or lower waypoint is free.
Implement fewest_climbs(height, trails, start) -> list[int]: element v is the minimum number of climbs needed to get from start to v, or -1 if v can't be reached. The number of trails walked doesn't matter.
height = [5, 3, 8, 6, 9]
trails = [(0, 1), (1, 3), (3, 2), (0, 2), (2, 4)]
fewest_climbs(height, trails, 0)
# [0, 0, 1, 1, 2] 0 -> 2 is one climb; 0 -> 1 -> 3 is one climb (3 up to 6);
# 4 needs 0 -> 2 -> 4, two climbs
Constraints: 1 <= n <= 10^5, up to 2 * 10^5 trails, heights are integers. Plain BFS counts trails, not climbs, so it gives wrong answers; and Bellman-Ford is far too slow at this size.
Show hint
every edge weight is 0 or 1, so use 0-1 BFS: a deque where a free move is pushed to the front and a climb to the back. (Dijkstra also works, just with a log factor.)