Loading...
Loading...
Loading...
A truck must go from town 1 to town n. Each two-way road "a b w" has a weight limit w. The truck may use only roads whose limit is at least its own weight, so what matters on a route is its lowest limit. Since the truck should be as heavy as possible, print the highest possible weight of a truck that can still drive from town 1 to town n, or -1 if the towns are not connected at all.
Example
Input
4 4 1 2 5 2 4 3 1 3 2 3 4 9
Output
3
Route 1-2-4 has lowest limit 3; route 1-3-4 has lowest limit 2.
Try the problem first. Open one hint at a time.
Sort the roads from the highest limit down and join their towns with Union-Find.
The limit of the road that first connects town 1 and town n is the answer.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor