PreviousNext
Coding/Graphs and trees

Second-shortest path distance

Write codeHard40 min

Your task

Given an undirected weighted graph with n nodes (0..n-1) and edges [u, v, w] with positive weights, return the length of the strictly second-shortest path distance from a source to a destination. Walks may revisit nodes and edges, so the second-shortest value may be strictly larger than the shortest even when only one simple route exists. Return -1 if no second distinct distance exists. Constraints: 1 <= n <= 500.

Examples

second_shortest_path(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputsecond_shortest_path(3, [[0, 1, 1], [1, 2, 1], [0, 2, 4]], 0, 2)
Output4