98. Shortest Paths With Negative Edges (Bellman-Ford)
MediumGraphs
A directed graph has n vertices (0 to n − 1) and weighted edges [u, v, w]; weights may be negative. Return an array dist where dist[i] is the shortest distance from src to i, or null if i cannot be reached.
If a negative-weight cycle can be reached from src, shortest distances are undefined: return null instead of an array.
Example 1
Input: n = 3, edges = [[0,1,4],[0,2,5],[1,2,-2]], src = 0 Output: [0, 4, 2]
Example 2
Input: n = 3, edges = [[0,1,1],[1,2,-1],[2,1,-1]], src = 0 Output: null
Constraints
1 ≤ n ≤ 5000 ≤ edges.length ≤ 5000