The road you can't avoid
Find the route between two places whose most expensive road is as cheap as possible, by adding roads cheapest-first until the two meet. About 14 minutes.
Cheapest-first, but stop early
Think of a road trip where the only thing that bothers you is the single most expensive toll along the way. You want a route whose most expensive toll is as low as possible.
Here's the trick: allow only roads up to some price, and see if the two places are connected. Start with the cheapest roads and allow more and more expensive ones. The moment the two places become connected, the price you just allowed is the smallest worst toll. That's the same cheapest-first process as before, and we stop early.
roads.sort(key=lambda r: r[2])
- allowed
- 2
Allow roads up to 2: just 1 to 2. Places 0 and 5 are not connected yet.
Edge cases
If the two places are the same place, you don't need any road, so the worst toll is 0. Check that before anything else.
And if you go through every road and the two places are still not connected, no route exists at all, so the answer is -1. Notice that you merge groups for every road in order, even those whose ends are already connected, which does no harm.
if find(a) == find(b):
return w # the road that joinedWhile adding roads in order of price, the two places you care about become connected right after a road costing 6. What is the answer?
- A6, the road that finally connected them
- BThe sum of all the roads added so far
- CThe cheapest road, because it was added first
Show the answer
6, the road that finally connected them. Before it they couldn't be connected using cheaper roads, and after it they can.
Smallest worst road
There are n places, numbered 0 to n − 1. roads[i] = [x, y, cost] is a two-way road between place x and place y. A route between two places is judged by its most expensive road. Return the smallest possible cost of the most expensive road over all routes from place a to place b. Return 0 if a equals b, and -1 if there is no route.
n = 6, roads = [[0, 1, 4], [1, 2, 2], [0, 2, 7], [2, 5, 6], [1, 3, 3], [3, 4, 5], [4, 5, 9], [3, 5, 8]], a = 0, b = 5 → 6
1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000 · 1 ≤ cost ≤ 1,000,000