All Pairs Shortest Path

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 0.4s

Java 2.0s

Memory limit: 512M

Author:

wleung_bvg

Problem types

You are given a graph with $N$ $N$ vertices and $M$ $M$ edges. Each edge is a directed edge from vertex $u_i$ $u_{i}$ to vertex $v_i$ $v_{i}$ with weight $w_i$ $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$ $0 \leq M \leq 4 000$

$1 \le u_i, v_i \le N$ $1 \leq u_{i}, v_{i} \leq N$

Subtask 1 [10%]

$1 \le N \le 300$ $1 \leq N \leq 300$

$-10^9 \le w_i \le 10^9$ $- 10^{9} \leq w_{i} \leq 10^{9}$

Subtask 2 [10%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

$1 \le w_i \le 10^9$ $1 \leq w_{i} \leq 10^{9}$

Subtask 3 [80%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

$-10^9 \le w_i \le 10^9$ $- 10^{9} \leq w_{i} \leq 10^{9}$

Input Specification

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

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

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

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

Sample Input 1

Copy

Sample Output 1

Copy

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

Copy

Sample Output 2

Copy

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

0

stanwww commented on Oct. 30, 2024, 4:05 a.m.

I need hints.

4

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

Floyd-Warshall passes, which is probably not intended.

5

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

Time limits have been adjusted.