All Pairs Shortest Path

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.4s
Java 2.0s
Memory limit: 512M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are given a graph with N vertices and M edges. Each edge is a directed edge from vertex u_i to vertex v_i with weight w_i. 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,

0 \le M \le 4\,000

1 \le u_i, v_i \le N

Subtask 1 [10%]

1 \le N \le 300

-10^9 \le w_i \le 10^9

Subtask 2 [10%]

1 \le N \le 1\,000

1 \le w_i \le 10^9

Subtask 3 [80%]

1 \le N \le 1\,000

-10^9 \le w_i \le 10^9

Input Specification

The first line contains 2 integers N and M, subject to the constraints above.

The next M lines describe the edges of the graph. Each line contains 3 integers, u_i, v_i, w_i, indicating a directed edge from vertex u_i to vertex v_i with weight w_i, 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 N lines, each with N space separated integers. Each line should end with a new line character. Integer j on line i contains the distance of the shortest path from vertex i to vertex j.

If there is no path from i to j, INF should be printed instead of an integer.

If there is no lower bound on the length of the shortest path from i to j (or equivalently, there is a path from i to j 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 that 0.

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


  • 4
    Dingledooper  commented on March 10, 2020, 12:59 a.m.

    Floyd-Warshall passes, which is probably not intended.


    • 4
      wleung_bvg  commented on March 10, 2020, 4:52 a.m.

      Time limits have been adjusted.