1029. Floyd-Warshall All-Pairs Shortest Path

Given a directed weighted graph with n nodes and edges [u, v, w] (non-negative), return the n x n matrix of shortest-path distances between every ordered pair (distance 0 on the diagonal, -1 where no path exists). The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, w].

Output: Nested array — the all-pairs distance matrix.

Examples

Input: {"n":3,"edges":[[0,1,4],[0,2,1],[2,1,2]]}
Output: [[0,3,1],[-1,0,-1],[-1,2,0]]
Explanation: All-pairs shortest distances.

Input: {"n":1,"edges":[]}
Output: [[0]]
Explanation: Single node.

Input: {"n":2,"edges":[[0,1,5]]}
Output: [[0,5],[-1,0]]
Explanation: One directed edge.

Constraints

• 1<=n<=500
• directed

Asked by