1645. The Route With the Smallest Worst Edge
An undirected graph has weights meaning "how bad this edge is". A route is judged by its WORST edge, not by its total.
Print the smallest possible worst edge over all routes from vertex 1 to vertex
n, or -1 if there is no route. Print 0 when n is 1, since a route of no
edges has no worst edge.
Every shortest-path algorithm so far has added weights along the route. Change the measure from sum to maximum and Dijkstra's argument does not survive unchanged, so the natural move is to stop optimising and start testing:
can vertex 1 reach vertex n using only edges of weight <= x ?
That question is monotonic. If x works then anything larger works too, because
raising the threshold only ever adds edges. So the set of workable thresholds is
everything above some boundary, and the answer is that boundary.
Sorting the edges and adding them cheapest first finds it directly: the answer is
the weight of the edge whose addition first joins 1 to n. A disjoint set, the
structure from problem 986, answers "are these joined yet" as each edge arrives.
This is the same insight as a minimum spanning tree, which is why #389 and this are relatives rather than the same question.
Constraints - `1 ≤ n ≤ 10000` - `0 ≤ m ≤ 50000` - `0 ≤ w ≤ 1000000000`
Input
The first line contains two integers n and m.
Each of the next m lines contains three integers u, v and w: an undirected edge between u and v of weight w.
Output
Print the smallest possible worst edge on a route from 1 to n, or -1 if there is no route.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.