Floyd-Warshall: All Pairs

A directed graph has n nodes and weighted edges [a, b, w] with w >= 0. Return an n x n matrix where entry [i][j] is the shortest distance from i to j, with -1 if j cannot be reached from i. The distance from a node to itself is 0.

For n = 3 and edges = [[0, 1, 4], [1, 2, 1], [0, 2, 7]] the answer is [[0, 4, 5], [-1, 0, 1], [-1, -1, 0]].

Examples

Example 1

Input:

all_pairs_shortest(3, [[0, 1, 4], [1, 2, 1], [0, 2, 7]])

Output:

[[0, 4, 5], [-1, 0, 1], [-1, -1, 0]]

Example 2

Input:

all_pairs_shortest(2, [])

Output:

[[0, -1], [-1, 0]]

Constraints

• 1 <= n <= 120
• 0 <= len(edges) <= 3000
• 0 <= w <= 10**4