import java.io.*;
import java.util.*;
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;
                    pMatrix[i][j] = -1; // No direct path
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    pMatrix[i][j] = i != j ? 0 : -1; // Self-loop and Direct path logic adjusted
                }
            }
        }
    }
    
    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
        
        // Initialize pMatrix for direct paths and self-loops
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || adjMatrix[i][j] == Integer.MAX_VALUE) {
                    pMatrix[i][j] = -1; // No path initially
                } else {
                    pMatrix[i][j] = i; // Direct path exists, storing predecessor
                }
            }
        }
    
        // Apply Floyd-Warshall algorithm
        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) {
                        long newPathDist = (long)adjMatrix[i][k] + adjMatrix[k][j];
                        if (newPathDist < adjMatrix[i][j]) {
                            adjMatrix[i][j] = (int)newPathDist;
                            pMatrix[i][j] = pMatrix[k][j]; // Store the penultimate vertex before j
                        }
                    }
                }
            }
        }
    }
    
    private static void printResult(int problemCount, int n) throws FileNotFoundException, IOException {
        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++) {
                    if (i == j) {
                        out.print("0 ");
                    } else {
                        // Print the number of the node just before destination on the shortest path
                        out.print((pMatrix[i][j] != -1 ? (pMatrix[i][j] + 1) : "-") + " ");
                    }
                }
                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
        }
    }
        
    

    private static String getShortestPath(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) {
            return "No path";
        }
    
        List<Integer> path = new ArrayList<>();
        for (int at = dest; at != -1; at = pMatrix[source][at]) {
            path.add(at); // Collect in reverse order
        }
        Collections.reverse(path); // Reverse to get the correct order starting from source
    
        // Build the output
        StringBuilder pathStr = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) pathStr.append(" ");
            pathStr.append("V").append(path.get(i) + 1); // Add 1 for 1-indexed vertex numbering
        }
    
        return pathStr.toString();
    }
    
} I want the program to read the input 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 correctly then initialize the Pmatrix such that if there is a direct path or self form the source node to the destination node then it should be represented by 0, if there is no direct path then initialize it as the destination node itself. Then calculate the shortest path in the cases where there is no direct path between the source node and the destination node. Then update the Pmatrix with the node just before the destination node where no direct path was found initially.