Floyd - existence#976
Given a directed weighted graph, determine for each pair of vertices, using its adjacency matrix, whether a shortest path exists between them.
A shortest path between two vertices may not exist for two reasons:
There is no path between the vertices.
There exists a path with arbitrarily small total weight (i.e., there is a cycle with negative total weight reachable from the start vertex to the end vertex).
The first line contains the number of vertices (1 \le n \le 100). Each of the next lines contains integers, representing the adjacency matrix: the -th number in the -th row is the weight of the edge from vertex to vertex . In the matrix, the number indicates that there is no edge (for i \neq j), while any other number denotes the presence of an edge with the corresponding weight. All the numbers are integers with absolute values not exceeding .
Print lines with integers each: the -th number on the -th line should be if there is no path from vertex to vertex ; if a shortest path exists; and if there is a path from vertex to vertex of arbitrarily small total weight.
Example 1