Weight Limit
Time limit1sMemory limit128 MB
Given a weighted undirected graph, find the maximum possible minimum edge weight (bottleneck) along any path between two given nodes.
- Level
Medium5 of 10
- Topics
- Union-find, Binary search, Graph
- Solved
- No attempts yet
Problem
A country consists of N islands. Some pairs of islands are connected by bidirectional bridges that vehicles can use, and each bridge has a maximum cargo weight that can pass over it at one time.
There is one factory on each of two different islands. To move goods from one factory to the other, every bridge on the chosen route must be able to support the carried weight. If the cargo is heavier than a bridge's limit, that bridge collapses.
Find the maximum weight of goods that can be transported in one trip between the two factories.
Input
The first line contains the number of islands N and the number of bridges M. 2 <= N <= 10,000 and 1 <= M <= 100,000.
Each of the next M lines contains three integers A, B, and C, describing a bidirectional bridge between island A and island B with weight limit C. 1 <= A, B <= N and 1 <= C <= 1,000,000,000. There may be multiple bridges between the same pair of islands.
The last line contains the two different island numbers where the factories are located. The input always guarantees that at least one route connects the two factories.
Output
Print the maximum weight of goods that can be transported in one trip between the two factories.