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


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;
                    pMatrix[i][j] = -1; // No direct path
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    if (i != j && adjMatrix[i][j] < Integer.MAX_VALUE) {
                        pMatrix[i][j] = i; // Direct path from i to j, so predecessor is j itself
                    } else if (i == j) {
                        pMatrix[i][j] = -1; // Optional: Self loops don’t need a predecessor
                        adjMatrix[i][j] = 0; // Distance from a node to itself is 0
                    }
                }
            }
        }
    }
    

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
        // Initialize pMatrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (adjMatrix[i][j] == Integer.MAX_VALUE || i == j) {
                    pMatrix[i][j] = -1; // No path or self-loop
                } else {
                    pMatrix[i][j] = i; // Predecessor initially set to source node
                }
            }
        }
        
        // Calculate shortest paths and update pMatrix
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE && adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j]) {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                        pMatrix[i][j] = pMatrix[i][k]; // Set the predecessor of j as the predecessor of k for the path from i to j.
                    }
                }
            }
        }
    }

    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";
        }
    
        // Use a list to construct the path in reverse
        LinkedList<String> pathList = new LinkedList<>();
        int currentNode = dest;
    
        while (currentNode != source) {
            pathList.addFirst("V" + (currentNode + 1));
            currentNode = pMatrix[source][currentNode];
        }
        // Add the source node at the beginning
        pathList.addFirst("V" + (source + 1));
        
        // Join the path list with spaces
        return String.join(" ", pathList);
    }
    

    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 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 and the output is Problem1: n = 7
Pmatrix:
-1  0  0  0  0  0  0 
 1 -1  1  1  1  1  1 
 2  2 -1  2  2  2  2 
 3  3  3 -1  3  3  3 
 4  4  4  4 -1  4  4 
 5  5  5  5  5 -1  5 
 6  6  6  6  6  6 -1 

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:
-1  0  0  0  0  0 
 1 -1  1  1  1  1 
 2  2 -1  2  2  2 
 3  3  3 -1  3  3 
 4  4  4  4 -1  4 
 5  5  5  5  5 -1 

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 the expected 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

The output that the program is giving now has incorrect Pmatrix. The correct Pmatrix that the program should provide is shown in the expected output. Take an example of  Problem1. In Problem1: n = 7
Pmatrix:
-1  0  0  0  0  0  0 
 1 -1  1  1  1  1  1 
 2  2 -1  2  2  2  2 
 3  3  3 -1  3  3  3 
 4  4  4  4 -1  4  4 
 5  5  5  5  5 -1  5 
 6  6  6  6  6  6 -1  but the correct Pmatrix 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 . In the correct Pmatrix there is the intermediate node through which it is passing on the place of a number except for the places denoted by 0. Consider for V1, 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 and in correct Pmatrix the first row is 0  0  0  6  3  0  6 . Here, wherever there is a direct path form V1 to Vj or another node that place is denoted by 0 in the Pmatrix and where there is an intermediate node from V1 to Vj or another node that place is denoted by the number of that intermediate node such as for this path V1 V6 V4: 4, in the correct Pmatrix at 4th position in the first row 6 is represented as V1 goes to V4 through V6.