progress

~/problems / More shortest paths

Fewest climbs on the hiking trails

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~20 min

A park has waypoints 0 .. n-1 at altitudes height[v], joined by two-way trails (a, b). A tired hiker only counts climbs: a trail to a strictly higher waypoint costs 1, anything else is free.

Implement fewest_climbs(height, trails, start) -> list[int]: for each v, the fewest climbs from start, or -1 if unreachable. Trail count 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

Up to 10^5 waypoints and 2 * 10^5 trails. Plain BFS counts trails, not climbs, so it's wrong.

⭐ Bonus: Bellman-Ford still passes; a speed test on a big park earns a star in O(n + trails).

Show hint

weights are 0 or 1, so use 0-1 BFS: a deque where free moves go to the front and climbs to the back (Dijkstra works too, with a log factor).

Topic: Bellman-Ford, Floyd-Warshall, 0-1 BFS. Negative edges, all-pairs, and deque BFS for 0/1 weights.

0:00
Ctrl ' run · Ctrl ↵ submit
esc