PROGRAMMING:Shortest path algorithm (Floyd Warshall)
In weighted digraph g, the problem of finding the shortest path between any pair of vertices in G is also a very common problem.
One way to solve this problem is to execute the Dijkstra algorithm n times, so that the shortest path between each pair of vertices can be found, and the execution time complexity is $$o (n ^ {3}) $.
The other algorithm is proposed by Freud, the time complexity is also $$o (n ^ {3}) $$, but the form of the algorithm is much simpler.
In this problem, read a weighted adjacency matrix (array representation) of a digraph, establish a digraph, and use Floyd algorithm to find the shortest path length between each pair of vertices.
###Input format:
The first line of input contains a positive integer n, indicating that there are n vertices in the graph. Where n does not exceed 50.
Each of the following N lines has n integers separated by spaces. For the j-th integer in the i-th row, if it is greater than 0, it means that the i-th vertex has a directed edge to the j-th vertex, and the weight is the corresponding integer value; If the integer is 0, then there is no directed edge where I points to J.
When I and j are equal, ensure that the corresponding integer is 0.
###Output format:
There are n rows in total, and each row has n integers, indicating the shortest path length from the source point to each vertex.
If there is no path from the source point to the corresponding vertex, output - 1. For the shortest path length from a vertex to itself, output 0.
Please output a space after each integer, and pay attention to the end of the line output newline.
###Input example:
```in
four
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
```
###Output example:
```out
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0
```
answer：If there is no answer, please comment
One way to solve this problem is to execute the Dijkstra algorithm n times, so that the shortest path between each pair of vertices can be found, and the execution time complexity is $$o (n ^ {3}) $.
The other algorithm is proposed by Freud, the time complexity is also $$o (n ^ {3}) $$, but the form of the algorithm is much simpler.
In this problem, read a weighted adjacency matrix (array representation) of a digraph, establish a digraph, and use Floyd algorithm to find the shortest path length between each pair of vertices.
###Input format:
The first line of input contains a positive integer n, indicating that there are n vertices in the graph. Where n does not exceed 50.
Each of the following N lines has n integers separated by spaces. For the j-th integer in the i-th row, if it is greater than 0, it means that the i-th vertex has a directed edge to the j-th vertex, and the weight is the corresponding integer value; If the integer is 0, then there is no directed edge where I points to J.
When I and j are equal, ensure that the corresponding integer is 0.
###Output format:
There are n rows in total, and each row has n integers, indicating the shortest path length from the source point to each vertex.
If there is no path from the source point to the corresponding vertex, output - 1. For the shortest path length from a vertex to itself, output 0.
Please output a space after each integer, and pay attention to the end of the line output newline.
###Input example:
```in
four
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
```
###Output example:
```out
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0
```
answer：If there is no answer, please comment