import java.io.*;
import java.util.Scanner;


public class floyd {
    private static int[][] adjMatrix;
    private static int[][] pMatrix;
    private static final String OUTPUT_FILE = "output.txt";

    public static void main(String[] args) throws IOException {
        if (args.length != 1) {
            System.err.println("Usage: java Floyd <graph-file>");
            return;
        }

        try (Scanner scanner = new Scanner(new BufferedReader(new FileReader(args[0])))) {
            createFile();

            int problemCount = 0;

            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();

                if (line.startsWith("Problem")) {
                    problemCount++;
                    int n = extractNumberOfVertices(line);

                    if (n < 5 || n > 10) {
                        throw new IllegalArgumentException("Invalid number of vertices.");
                    }

                    // Read adjacency matrix for the current problem
                    initializeMatrices(n, scanner);

                    // Compute shortest paths and print results
                    calculateShortestPaths();
                    printResult(problemCount, n);
                }
            }
        }
    }

    private static void createFile() throws FileNotFoundException {
        PrintWriter writer = new PrintWriter(OUTPUT_FILE);
        writer.close();
    }

    private static int extractNumberOfVertices(String line) {
        // Extracts the number of vertices from the line
        String[] parts = line.split("n = ");
        return Integer.parseInt(parts[1].trim());
    }

    private static void initializeMatrices(int n, Scanner scanner) {
        adjMatrix = new int[n][n];
        pMatrix = new int[n][n];
    
        for (int i = 0; i < n; i++) {
            String[] values = scanner.nextLine().trim().split("\s+");
            for (int j = 0; j < n; j++) {
                if (values[j].equals("INF")) {
                    adjMatrix[i][j] = Integer.MAX_VALUE;
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    if (i != j && weight < Integer.MAX_VALUE) {
                        pMatrix[i][j] = j; // Direct path from i to j, so next hop toward j is j itself
                    } else {
                        pMatrix[i][j] = 0; // No direct path or self
                    }
                }
            }
        }
    }
    
    

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
    
        // Initialize Pmatrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Initialize Pmatrix to -1 indicating no path unless there is a direct path
                pMatrix[i][j] = 0;
    
                if (adjMatrix[i][j] != Integer.MAX_VALUE && i != j) {
                    // Direct path from i to j, set next hop to j
                    pMatrix[i][j] = j;
                }
            }
        }
    
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Check if path i -> k -> j is shorter than the current i -> j
                    if (adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE) {
                        long ik_kj_path = ((long) adjMatrix[i][k]) + adjMatrix[k][j];
                        if (ik_kj_path < adjMatrix[i][j]) {
                            adjMatrix[i][j] = (int) ik_kj_path;
                            // Update pMatrix[i][j] to go through intermediate node k
                            pMatrix[i][j] = pMatrix[i][k];
                        }
                    }
                }
            }
        }
    }
    
    

    private static void printResult(int problemCount, int n) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.println("Problem" + problemCount + ": n = " + n);
            out.println("Pmatrix:");
            
            // Output the Pmatrix for the problem
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    out.print(String.format("%2d ", pMatrix[i][j]));
                }
                out.println();
            }
            out.println();
    
            // Output shortest paths for each city to all other cities
            for (int source = 0; source < n; source++) {
                out.println("V" + (source + 1) + "-Vj: shortest path and length");
                for (int dest = 0; dest < n; dest++) {
                    // Get the shortest path and distance between the source and destination
                    String path = getShortestPath(source, dest);
                    int distance = adjMatrix[source][dest];
    
                    out.println(path + ": " + distance);
                }
                out.println();
            }
            out.println(); // Separate problems visually
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
    

    private static String getShortestPath(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) {
            return "No path";
        }
    
        StringBuilder path = new StringBuilder("V" + (source + 1));
        int next = source;
        // Traverse from source to destination using Pmatrix to construct the path
        while (next != dest) {
            next = pMatrix[next][dest];
            if(next == -1) break; // Break if there’s no valid next step (should not happen in a correctly initialized Pmatrix)
            path.append(" V").append(next + 1);
        }
    
        return path.toString();
    }
    

    private static void appendToFile(String output) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.print(output);
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
}

The input for the above program is:

Problem1 Amatrix: n = 7
0  6  5  4  6  3  6  
6  0  6  4  5  5  3  
5  6  0  3  1  4  6  
4  4  3  0  4  1  4  
6  5  1  4  0  5  5  
3  5  4  1  5  0  3  
6  3  6  4  5  3  0  

Problem2 Amatrix: n = 6
0  1  2  1  3  4  
1  0  3  2  2  3  
2  3  0  3  3  6  
1  2  3  0  3  5  
3  2  3  3  0  5  
4  3  6  5  5  0

The output got by running the above program for the above input is:

Problem1: n = 7
Pmatrix:
 0  1  2  3  4  5  6 
 0  0  2  3  4  5  6 
 0  1  0  3  4  5  6 
 0  1  2  0  4  5  6 
 0  1  2  3  0  5  6 
 0  1  2  3  4  0  6 
 0  1  2  3  4  5  0 

V1-Vj: shortest path and length
V1: 0
V1 V2: 6
V1 V3: 5
V1 V4: 4
V1 V5: 6
V1 V6: 3
V1 V7: 6

V2-Vj: shortest path and length
V2 V1: 6
V2: 0
V2 V3: 6
V2 V4: 4
V2 V5: 5
V2 V6: 5
V2 V7: 3

V3-Vj: shortest path and length
V3 V1: 5
V3 V2: 6
V3: 0
V3 V4: 3
V3 V5: 1
V3 V6: 4
V3 V7: 6

V4-Vj: shortest path and length
V4 V1: 4
V4 V2: 4
V4 V3: 3
V4: 0
V4 V5: 4
V4 V6: 1
V4 V7: 4

V5-Vj: shortest path and length
V5 V1: 6
V5 V2: 5
V5 V3: 1
V5 V4: 4
V5: 0
V5 V6: 5
V5 V7: 5

V6-Vj: shortest path and length
V6 V1: 3
V6 V2: 5
V6 V3: 4
V6 V4: 1
V6 V5: 5
V6: 0
V6 V7: 3

V7-Vj: shortest path and length
V7 V1: 6
V7 V2: 3
V7 V3: 6
V7 V4: 4
V7 V5: 5
V7 V6: 3
V7: 0


Problem2: n = 6
Pmatrix:
 0  1  2  3  4  5 
 0  0  2  3  4  5 
 0  1  0  3  4  5 
 0  1  2  0  4  5 
 0  1  2  3  0  5 
 0  1  2  3  4  0 

V1-Vj: shortest path and length
V1: 0
V1 V2: 1
V1 V3: 2
V1 V4: 1
V1 V5: 3
V1 V6: 4

V2-Vj: shortest path and length
V2 V1: 1
V2: 0
V2 V3: 3
V2 V4: 2
V2 V5: 2
V2 V6: 3

V3-Vj: shortest path and length
V3 V1: 2
V3 V2: 3
V3: 0
V3 V4: 3
V3 V5: 3
V3 V6: 6

V4-Vj: shortest path and length
V4 V1: 1
V4 V2: 2
V4 V3: 3
V4: 0
V4 V5: 3
V4 V6: 5

V5-Vj: shortest path and length
V5 V1: 3
V5 V2: 2
V5 V3: 3
V5 V4: 3
V5: 0
V5 V6: 5

V6-Vj: shortest path and length
V6 V1: 4
V6 V2: 3
V6 V3: 6
V6 V4: 5
V6 V5: 5
V6: 0
But this output is incorrectly showing the Pmatrix.

The correct output is:
Problem1: n = 7
Pmatrix:
0 0 0 6 3 0 6
0 0 5 0 0 4 0
0 5 0 0 0 0 5
6 0 0 0 3 0 6
3 0 0 3 0 3 0
0 4 0 0 3 0 0
6 0 5 6 0 0 0

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 6
V1 V3: 5
V1 V6 V4: 4
V1 V3 V5: 6
V1 V6: 3
V1 V6 V7: 6

V2-Vj: shortest path and length
V2 V1: 6
V2 V2: 0
V2 V5 V3: 6
V2 V4: 4
V2 V5: 5
V2 V4 V6: 5
V2 V7: 3

V3-Vj: shortest path and length
V3 V1: 5
V3 V5 V2: 6
V3 V3: 0
V3 V4: 3
V3 V5: 1
V3 V6: 4
V3 V5 V7: 6

V4-Vj: shortest path and length
V4 V6 V1: 4
V4 V2: 4
V4 V3: 3
V4 V4: 0
V4 V3 V5: 4
V4 V6: 1
V4 V6 V7: 4

V5-Vj: shortest path and length
V5 V3 V1: 6
V5 V2: 5
V5 V3: 1
V5 V3 V4: 4
V5 V5: 0
V5 V3 V6: 5
V5 V7: 5

V6-Vj: shortest path and length
V6 V1: 3
V6 V4 V2: 5
V6 V3: 4
V6 V4: 1
V6 V3 V5: 5
V6 V6: 0
V6 V7: 3

V7-Vj: shortest path and length
V7 V6 V1: 6
V7 V2: 3
V7 V5 V3: 6
V7 V6 V4: 4
V7 V5: 5
V7 V6: 3
V7 V7: 0

Problem2: n = 6
Pmatrix:
0 0 0 0 2 2
0 0 1 1 0 0
0 1 0 1 0 2
0 1 1 0 0 2
2 0 0 0 0 2
2 0 2 2 2 0

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 1
V1 V3: 2
V1 V4: 1
V1 V2 V5: 3
V1 V2 V6: 4

V2-Vj: shortest path and length
V2 V1: 1
V2 V2: 0
V2 V1 V3: 3
V2 V1 V4: 2
V2 V5: 2
V2 V6: 3

V3-Vj: shortest path and length
V3 V1: 2
V3 V1 V2: 3
V3 V3: 0
V3 V1 V4: 3
V3 V5: 3
V3 V1 V2 V6: 6

V4-Vj: shortest path and length
V4 V1: 1
V4 V1 V2: 2
V4 V1 V3: 3
V4 V4: 0
V4 V5: 3
V4 V1 V2 V6: 5

V5-Vj: shortest path and length
V5 V2 V1: 3
V5 V2: 2
V5 V3: 3
V5 V4: 3
V5 V5: 0
V5 V2 V6: 5

V6-Vj: shortest path and length
V6 V2 V1: 4
V6 V2: 3
V6 V2 V1 V3: 6
V6 V2 V1 V4: 5
V6 V2 V5: 5
V6 V6: 0 

In the correct output the Pmatrix is correct and the program is expected to print the same Pmatrix. Consider the Problem1: n = 7 of the correct output.
Problem1: n = 7
Pmatrix:
0 0 0 6 3 0 6
0 0 5 0 0 4 0
0 5 0 0 0 0 5
6 0 0 0 3 0 6
3 0 0 3 0 3 0
0 4 0 0 3 0 0
6 0 5 6 0 0 0

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 6
V1 V3: 5
V1 V6 V4: 4
V1 V3 V5: 6
V1 V6: 3
V1 V6 V7: 6


Here, understand the V1-Vj shortest path and then consider the 1st row of the Pmatix for Problem1: n = 7. In the 1st row, the first 3 columns representing V1, V2, V3 are denoted by 0 as there is a direct path from V1 to V1, V2, V3. Consider the 4th column represented by V4, it is denoted by 6 as the shortest path from V1 to V4 goes through V6. Similarly the 5th column represented by V5, is denoted by 3 as the shortest path from V1 to V5 goes through V3. Similarly the 7th column represented by V7, is denoted by 6 as the shortest path from V1 to V7 goes through V6.

Make changes to the code such that it constructs the Pmatrix according to the above described logic.