All-pairs shortest paths DAG
Your task
You are given a directed acyclic graph on n nodes (0..n-1) with edges [u, v, w] where weights may be negative (the graph is a DAG, so there are no cycles and hence no negative cycles). Return the all-pairs shortest-distance matrix res where res[i][j] is the shortest distance from i to j, res[i][i] = 0, and res[i][j] = 1000000000 (one billion) if j is unreachable from i. Constraints: 1 <= n <= 150; -1000 <= w <= 1000.
Examples
johnson_apsp(n: int, edges: list[list[int]]) -> list[list[int]]Example 1
Input
johnson_apsp(4, [[0, 1, 4], [1, 2, -2], [2, 3, 3], [0, 3, 5]])Output
[[0, 4, 2, 5], [1000000000, 0, -2, 1], [1000000000, 1000000000, 0, 3], [1000000000, 1000000000, 1000000000, 0]]