PreviousNext
Coding/Graphs and trees

Shortest path negative weights

Write codeMedium25 min

Your task

A directed graph on n nodes (0..n-1) has edges given as [u, v, w] where w may be negative. The graph contains NO negative cycle. Return the length of the shortest path from node s to node t, or -1 if t is unreachable. Because edges can be negative, plain Dijkstra is invalid. Constraints: 1 <= n <= 500; -1000 <= w <= 1000.

Examples

shortest_path_neg(n: int, edges: list[list[int]], s: int, t: int) -> int
Example 1
Inputshortest_path_neg(5, [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 4], [1, 3, 8], [3, 4, 2]], 0, 4)
Output7