Lowest High Pass
A region has n huts numbered 0 to n - 1. passes is a list of entries [a, b, height] with a != b: a mountain pass between huts a and b that can be crossed in both directions and climbs to altitude height. Several passes may join the same two huts, possibly at different heights.
A trek from start to goal is rated by the highest pass it crosses. Return the lowest possible rating over all treks from start to goal. Return 0 when start == goal and -1 when goal cannot be reached from start.
Example 1
n 4
passes [[0,1,5],[1,3,9],[0,2,7],[2,3,6]]
start 0
goal 3
returns 7
Going through hut 2 crosses passes of heights 7 and 6, rated 7; going through hut 1 is rated 9.
Example 2
n 3
passes [[0,1,4]]
start 0
goal 2
returns -1
Hut 2 has no pass at all.
Constraints
1 <= n <= 500 <= len(passes) <= 1000 <= a, b <= n - 1anda != b1 <= height <= 1000 <= start, goal <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium
- Rectangular IslandsMedium
- Rounds of Parallel JobsMedium
- Sealed RoomsMedium
- Smallest Task OrderMedium
- Smallest Team SplitMedium
- Steps to the ExitMedium