Loading...
Loading...
Loading...
A student cycles from her PG to college through a hilly town with n junctions, numbered 1 to n. Each road joins two junctions in both directions and has a climb: how hard it is to ride.
The effort of a route is the climb of its hardest road, not the total. Find a route from junction s to junction t with the smallest possible effort and print that effort. If s and t are the same junction, print 0. If no route exists, print -1.
Example 1
Input
4 4 1 2 5 2 4 5 1 3 1 3 4 7 1 4
Output
5
The route 1 → 3 → 4 is shorter in total (8 against 10) but its hardest road is 7. The route 1 → 2 → 4 has effort 5.
Example 2
Input
5 3 1 2 4 2 3 6 4 5 1 1 5
Output
-1
No road leads from the part with junction 1 to the part with junction 5.
Try the problem first. Open one hint at a time.
This looks like a shortest path, but a route is judged by its hardest road. Going from a route with effort e along a road with climb w gives effort max(e, w).
Like a total, this effort never goes down as the route gets longer. So the junction with the smallest known effort can be finished first.
Use a PriorityQueue of {effort, junction} and relax with Math.max instead of +. Skip entries that are worse than the best known.
Stop when t comes out of the queue, not when it is first added, because a better route may still be found.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor