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

public class floyd {
    private static int[][] adjMatrix;
    private static int[][] pMatrix;
    private static final String OUTPUT_FILE = "output.txt";
    private static ArrayList<Integer> path = new ArrayList<>();

    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();

            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();
                if (line.startsWith("Problem")) {
                    // Extract number of vertices from the line
                    int n = Integer.parseInt(line.split("n = ")[1].trim());
                    if (n < 5 || n > 10) {
                        throw new IllegalArgumentException("Invalid number of vertices.");
                    }

                    // Read and initialize the adjacency matrix for the current problem
                    initializeMatrices(n, scanner);
                    
                    // Compute shortest paths and print results
                    calculateShortestPaths();
                    printResult(n);
                }
            }
        }
    }

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

    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) {
            if (!scanner.hasNextLine()) {
                throw new IllegalStateException("Expected adjacency matrix row is missing.");
            }
            String[] values = scanner.nextLine().trim().split("\s+");
            for (int j = 0; j < n; ++j) {
                int weight = Integer.parseInt(values[j]);
                adjMatrix[i][j] = weight;
                if (weight < 0 || weight > 10) {
                    throw new IllegalArgumentException("Edge weight must be between 0 and 10.");
                }
                if (i == j) {
                    adjMatrix[i][j] = 0;
                } else if (weight != 0) {
                    pMatrix[i][j] = j;
                }
            }
        }
    }

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;

        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] + adjMatrix[k][j] < adjMatrix[i][j]) {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                        pMatrix[i][j] = pMatrix[i][k];
                    }
                }
            }
        }
    }

    private static String getFullPathAsString(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) return "No path";
        StringBuilder pathBuilder = new StringBuilder("V" + (source + 1));
        while (source != dest) {
            source = pMatrix[source][dest];
            pathBuilder.append(" V").append(source + 1);
        }
        return pathBuilder.toString();
    }

    private static void printResult(int n) throws FileNotFoundException {
        StringBuilder builder = new StringBuilder();
    
        for (int source = 0; source < n; ++source) {
            builder.append("Problem").append(source + 1).append(": n = ").append(n).append('\n');
            builder.append("Pmatrix:\n");
    
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    builder.append(formatElement(pMatrix[i][j])).append(" ");
                }
                builder.append("\n");
            }
    
            builder.append("\n");
    
            for (int dest = 0; dest < n; ++dest) {
                if (source != dest) { // Skip self to self paths
                    builder.append("V").append(source + 1).append("-V").append(dest + 1).append(": shortest path and length\n");
                    String pathStr = getFullPathAsString(source, dest);
                    builder.append(pathStr)
                            .append(": ")
                            .append(adjMatrix[source][dest])
                            .append("\n");
                }
            }
    
            builder.append("\n\n"); // Separate problems visually
            appendToFile(builder.toString());
            builder.setLength(0); // Reset builder for next problem
        }
    }

    private static boolean isDirectlyConnected(int from, int to) {
        return pMatrix[from][to] == to && adjMatrix[from][to] > 0;
    }
    
    private static String getShortestPathAsString(int source, int destination) {
        if (adjMatrix[source][destination] == Integer.MAX_VALUE) {
            return "No path";
        }
        int intermediate = pMatrix[source][destination];
        StringBuilder pathBuilder = new StringBuilder();
        pathBuilder.append("V").append(source + 1);
        while (source != destination) {
            pathBuilder.append(" V").append(intermediate + 1);
            source = intermediate;
            intermediate = pMatrix[source][destination];
        }
        return pathBuilder.toString();
    }
    

    private static void buildPath(int current, int destination) {
        path.clear();
        if (current != destination) {
            path.add(current);
            while (pMatrix[current][destination] != destination) {
                current = pMatrix[current][destination];
                path.add(current);
            }
            path.add(destination);
        }
    }

    private static void clearPathList() {
        path.clear();
    }

    private static String formatElement(int element) {
        return "%2d ".formatted(element);
    }

    private static void appendToFile(String string) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.println(string);
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
} The program is giving output as 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-V2: shortest path and length
V1 V2: 6
V1-V3: shortest path and length
V1 V3: 5
V1-V4: shortest path and length
V1 V4: 4
V1-V5: shortest path and length
V1 V5: 6
V1-V6: shortest path and length
V1 V6: 3
V1-V7: shortest path and length
V1 V7: 6



Problem2: 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  

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



Problem3: 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  

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



Problem4: 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  

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



Problem5: 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  

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



Problem6: 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  

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



Problem7: 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  

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



Problem1: 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-V2: shortest path and length
V1 V2: 1
V1-V3: shortest path and length
V1 V3: 2
V1-V4: shortest path and length
V1 V4: 1
V1-V5: shortest path and length
V1 V5: 3
V1-V6: shortest path and length
V1 V6: 4



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  

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



Problem3: 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  

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



Problem4: 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  

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



Problem5: 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  

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



Problem6: 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  

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

which is incorrect. 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

Understand the format of the expected output and make necessary changes to the program to achieve it. Output is the solution of problem 1 first, then problem 2, and etc. The solution of problem j(for eg. from V1 to all other cities should indicate as V1-Vj: shortest path and length first and then print the shortest path and distance to each city as shown in the expected output) should start with an integer n (the number cities) and the n x n Pointer Array P (in the next n rows). The shortest paths should then follow, one per line. Output the shortest paths from C1 to all other cities, then C2 to all other cities, and Cn to all other cities.