PreviousNext
Coding/Graphs and trees

Shortest path 0-1 weights

Write codeMedium25 min

Your task

An undirected graph on n nodes (0..n-1) has edges given as [u, v, w] where each weight w is either 0 or 1. Return the minimum-weight path length from s to t, or -1 if t is unreachable. You should achieve O(V + E) rather than a log factor. Constraints: 1 <= n <= 10^4; w in {0, 1}.

Examples

zero_one_bfs(n: int, edges: list[list[int]], s: int, t: int) -> int
Example 1
Inputzero_one_bfs(5, [[0, 1, 1], [1, 2, 0], [2, 3, 1], [3, 4, 0], [0, 4, 1], [0, 3, 1]], 0, 4)
Output1