PreviousNext
Coding/Graphs and trees

Shortest path minimum hops

Write codeMedium30 min

Your task

An undirected graph on n nodes (0..n-1) has weighted edges [u, v, w] with positive weights. Among all shortest (minimum total weight) paths from s to t, return the minimum number of edges (hops) used by any such shortest path. Return -1 if t is unreachable. Constraints: 1 <= n <= 10^4; 1 <= w <= 10^6.

Examples

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