8601: GRL_1_C : All Pairs Shortest Path
[Creator : ]
Description
Input
An edge-weighted graph G (V, E).
$|V|\ |E|\ r$
$s_0\ t_0\ d_0$
$s_1\ t_1\ d_1$
$:$
$s_{|E|−1}\ t_{|E|−1}\ d_{|E|−1}$
$|V|$ is the number of vertices and $|E|$ is the number of edges in $G$. The graph vertices are named with the numbers $0, 1,..., |V|−1$ respectively. r is the source of the graph.
$s_i$ and $t_i$ represent source and target vertices of $i$-th edge (directed) and $d_i$ represents the cost of the $i$-th edge.
Output
If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value), print
in a line.
Otherwise, print
$D_{0,0}\ D_{0,1}\ ...\ D_{0,|V|−1}$
$D_{1,0}\ D_{1,1}\ ...\ D_{1,|V|−1}$
NEGATIVE CYCLE
in a line.
Otherwise, print
$D_{0,0}\ D_{0,1}\ ...\ D_{0,|V|−1}$
$D_{1,0}\ D_{1,1}\ ...\ D_{1,|V|−1}$
$\vdots$
$D_{|V|-1,0}\ D_{|V-1|,1}\ ...\ D_{|V|-1,|V|−1}$
The output consists of |V| lines. For each ith line, print the cost of the shortest path from vertex i to each vertex j (j=0,1,…|V|−1) respectively. If there is no path from vertex i to vertex j, print "INF". Print a space between the costs.
Constraints
$1 ≤ |V| ≤ 100$
$0 ≤ |E| ≤ 9900$
$-2 × 10^7 ≤ d_i ≤ 2 × 10^7$
There are no parallel edges
There are no self-loops
$0 ≤ |E| ≤ 9900$
$-2 × 10^7 ≤ d_i ≤ 2 × 10^7$
There are no parallel edges
There are no self-loops
Sample 1 Input
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7
Sample 1 Output
0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0
Sample 2 Input
4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7
Sample 2 Output
0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0
Sample 3 Input
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7
Sample 3 Output
NEGATIVE CYCLE
HINT
相同题目：GRL_1_C。