PreviousNext
Coding/Graphs and trees

Widest path capacity

Write codeHard30 min

Your task

Given a connected undirected graph with n nodes (0..n-1) and edges [u, v, w] where w (a positive integer) is the bandwidth/capacity of that link, return the maximum-bottleneck (widest) path capacity from src to dst: among all paths, the maximum over paths of the minimum edge weight along the path. Return -1 if dst is unreachable from src. You may assume src != dst. Assume 1 <= n <= 5000.

Examples

max_bottleneck_path(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputmax_bottleneck_path(4, [[0, 1, 4], [1, 3, 2], [0, 2, 3], [2, 3, 3]], 0, 3)
Output3