You are given a graph with vertices and
edges. Each edge is a directed edge from vertex
to vertex
with weight
. You are asked to find the shortest path between all pairs of vertices. The graph may contain multiple edges between any pair of vertices, as well as self-loops. There may also be negative edge weights. It is not guaranteed that the graph is connected.
Constraints
For all subtasks:
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
Input Specification
The first line contains 2 integers and
, subject to the constraints above.
The next lines describe the edges of the graph. Each line contains 3 integers,
,
,
, indicating a directed edge from vertex
to vertex
with weight
, subject to the constraints above.
Output Specification
This problem is graded with an identical
checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n
character.
The output consists of lines, each with
space separated integers. Each line should end with a new line character. Integer
on line
contains the distance of the shortest path from vertex
to vertex
.
If there is no path from to
,
INF
should be printed instead of an integer.
If there is no lower bound on the length of the shortest path from to
(or equivalently, there is a path from
to
that contains a negative edge cycle),
-INF
should be printed instead of an integer.
A negative edge cycle is a path that starts and ends on the same vertex, and the sum of the weights of those edges on that path is less than .
Sample Input 1
5 4
1 2 9
1 4 8
2 4 2
3 5 4
Sample Output 1
0 9 INF 8 INF
INF 0 INF 2 INF
INF INF 0 INF 4
INF INF INF 0 INF
INF INF INF INF 0
Sample Input 2
6 6
1 2 2
1 3 4
2 3 -10
3 5 1
5 6 2
6 5 -5
Sample Output 2
0 2 -8 INF -INF -INF
INF 0 -10 INF -INF -INF
INF INF 0 INF -INF -INF
INF INF INF 0 INF INF
INF INF INF INF -INF -INF
INF INF INF INF -INF -INF
Comments
I need hints.
Floyd-Warshall passes, which is probably not intended.
Time limits have been adjusted.