시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 256 MB | 14 | 6 | 6 | 85.714% |
A rookie programmer wrote a program in C++.
for (int w = 1; w < N; w = w + 1) { for (int u = 1; u < N; u = u + 1) { for (int v = 1; v < N; v = v + 1) { g[u][v] = min(g[u][v], g[u][w] + g[w][v]); } } }
The programmer launched his program on a set of graphs, and after some tedious waiting finally decided to take a look at the results. Which were, of course, disappointing. You guessed right --- the programmer wanted to calculate the matrix of the shortest distances between all nodes in the graph. However, the program was flawed. The programmer can fix everything himself, but waiting for the program to recalculate the results takes too much precious time. We suggest that you write a program that takes the results of the unlucky programmer's code and returns a matrix of the shortest distances.
The first line of the input file contains a single integer $N$ ($1 \leq N \leq 2\,000$). The $i$th of the following $N$ lines contains a sequence of $N$ numbers, with the $j$th number equal to the value $g[i][j]$ after running the algorithm provided above ($0 \le g[i][j] \le 9999$).
Print $N$ lines. The $i$th line must contain a sequence of space-separated numbers, with the $j$th number equal to the length of the shortest path in the graph between the nodes $i$ and $j$, or the number $9999$, if there is no path between these two nodes.
3 0 1 1 1 0 9999 1 9999 0
0 1 1 1 0 2 1 2 0