Shortest distances that flag negative cycles
Your task
Given a directed weighted graph with n nodes (0..n-1) and edges [u, v, w] where weights may be negative, compute the shortest distance from node src to every node. Return a list of length n: entry i is the shortest distance to i, or the string "INF" if unreachable, or the string "NEG" if the shortest distance is unbounded below because i is reachable through a negative-weight cycle. The source's distance is 0 (unless it itself sits on/after a negative cycle).
Examples
bellman_ford(n: int, edges: list[list[int]], src: int) -> listExample 1
Input
bellman_ford(5, [[0, 1, 6], [0, 2, 7], [1, 2, 8], [1, 3, 5], [1, 4, -4], [2, 3, -3], [2, 4, 9], [3, 1, -2], [4, 0, 2], [4, 3, 7]], 0)Output
[0, 2, 7, 4, -2]