Given a directed graph with nonnegative edge costs, find the minimum cost between every ordered pair of cities and print one minimum-cost route for each reachable pair. Multiple edges may connect the same ordered pair; only their cheapest cost can matter. The diagonal starts at zero, representing the empty route from a city to itself.
Floyd–Warshall with a next-hop matrix
distance[i][j] stores the best known cost from i to j. next[i][j] stores the first city after i on that route, or -1 when no route is known. For a direct edge i -> j, that first city is j.
When considering city k as an intermediate, a route through k costs distance[i][k] + distance[k][j]. If this is strictly cheaper than the current route, update both the cost and its first hop: the route from i to k begins with next[i][k], so the newly improved route from i to j has the same first hop. Strict improvement avoids replacing an existing route on ties. Because edge costs are nonnegative and the diagonal is zero, a shortest route can be chosen without cycles; following the first-hop entries therefore reaches the destination. Self-routes are not printed as paths, as required by the problem.
Use a finite long sentinel and skip a relaxation if either half-route is unreachable. This prevents adding the sentinel to a finite value. The cost matrix takes O(N^3) time to compute and O(N^2) space; printing all routes costs O(N^2 + total path output), or O(N^2) plus the number of emitted city labels.
The output consists of the cost matrix first, using 0 for unreachable pairs, then one route record for every ordered pair in row-major order. An unreachable pair and a pair with identical endpoints each have a single 0 line. Every other reachable pair has its number of cities followed by the city sequence, including both endpoints.
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static final long INF = Long.MAX_VALUE / 4;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int cityCount = input.nextInt();
int routeCount = input.nextInt();
long[][] distance = new long[cityCount][cityCount];
int[][] next = new int[cityCount][cityCount];
for (int i = 0; i < cityCount; i++) {
java.util.Arrays.fill(distance[i], INF);
java.util.Arrays.fill(next[i], -1);
distance[i][i] = 0;
}
for (int i = 0; i < routeCount; i++) {
int from = input.nextInt() - 1;
int to = input.nextInt() - 1;
long cost = input.nextLong();
if (cost < distance[from][to]) {
distance[from][to] = cost;
next[from][to] = to;
}
}
for (int middle = 0; middle < cityCount; middle++) {
for (int from = 0; from < cityCount; from++) {
if (distance[from][middle] == INF) {
continue;
}
for (int to = 0; to < cityCount; to++) {
if (distance[middle][to] == INF) {
continue;
}
long candidate = distance[from][middle] + distance[middle][to];
if (candidate < distance[from][to]) {
distance[from][to] = candidate;
next[from][to] = next[from][middle];
}
}
}
}
StringBuilder output = new StringBuilder();
for (int from = 0; from < cityCount; from++) {
for (int to = 0; to < cityCount; to++) {
if (to > 0) {
output.append(' ');
}
output.append(distance[from][to] == INF ? 0 : distance[from][to]);
}
output.append('\n');
}
int[] path = new int[cityCount + 1];
for (int from = 0; from < cityCount; from++) {
for (int to = 0; to < cityCount; to++) {
if (from == to || next[from][to] == -1) {
output.append("0\n");
continue;
}
int length = 0;
int current = from;
path[length++] = current;
while (current != to) {
current = next[current][to];
path[length++] = current;
}
output.append(length);
for (int i = 0; i < length; i++) {
output.append(' ').append(path[i] + 1);
}
output.append('\n');
}
}
System.out.print(output);
}
private static class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int position;
private int length;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
private long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
long value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
private int nextInt() throws IOException {
return (int) nextLong();
}
}
}