#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>

using namespace std;

const int INF = 1e9; // Assuming INF represents infinity

class floydGraphProcessor
{
public:
    void processInput(const string &line, ifstream &infile, ofstream &outfile)
    {
        // Extract problem number and matrix size
        size_t problem_position = line.find("Problem");
        if (problem_position == string::npos)
        {
            cerr << "Error extracting parameters. \n";
            return;
        }

        int problemNumber, n;
        sscanf(line.c_str() + problem_position, "Problem%d", &problemNumber);

        // Extracting n from the line
        size_t n_position = line.find("n = ");
        if (n_position == string::npos)
        {
            cerr << "Error: 'n =' not found.\n";
            return;
        }

        sscanf(line.c_str() + n_position, "n = %d", &n);

        // Resize output matrix to n x n
        vector<vector<int>> matrix(n, vector<int>(n));

        // Read n x n matrix values
        for (int i = 0; i < n; i++)
        {
            string r;
            getline(infile, r);
            istringstream iss(r);
            for (int j = 0; j < n; j++)
            {
                iss >> matrix[i][j];
            }
        }

        // Output to file
        outfile << "Problem " << problemNumber << ": n = " << n << endl;
        vector<vector<int>> dist = matrix;
        vector<vector<int>> P(n, vector<int>(n, 0));

        // 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 (k != i && k != j && (dist[i][j] >= dist[i][k] + dist[k][j]))
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        P[i][j] = k + 1;
                    }
                }
            }
        }

        // Output final Pmatrix to file
        outfile << "Pmatrix:" << endl;
        printPath(P, n, outfile);
        outfile << endl;

        // shortest paths and length to file
        for (int i = 0; i < n; i++)
        {
            outfile << "V" << i + 1 << "-Vj: shortest path and length" << endl;
            for (int j = 0; j < n; j++)
            {
                outfile << "V" << i + 1 << " ";
                if (i != j)
                {
                    outfile << "V" << j + 1 << " ";
                    int v = j;
                    while (P[i][v] != 0)
                    {
                        outfile << "V" << P[i][v] << " ";
                        v = P[i][v] - 1;
                    }
                }
                outfile << ": " << dist[i][j] << endl;
            }
        }
    }

private:
    void printPath(const vector<vector<int>> &P, int n, ofstream &outfile)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                outfile << P[i][j] << " ";
            }
            outfile << endl;
        }
    }
};

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        cerr << "Usage: " << argv[0] << " <input_file_path>" << endl;
        return 1;
    }

    ifstream infile(argv[1]);
    if (!infile.is_open())
    {
        cerr << "Error!. Wrong usage of the file, error opening the file. " << endl;
        cout << "Correct usage : " << argv[0] << " <input_file_path>" << endl;
        return 1;
    }

    ofstream outfile("output.txt");
    if (!outfile.is_open())
    {
        cerr << "Error opening output file." << endl;
        return 1;
    }

    string line;
    floydGraphProcessor processor;
    while (getline(infile, line))
    {
        size_t found = line.find("Problem");
        if (found != string::npos)
        {
            processor.processInput(line, infile, outfile);
        }
    }

    infile.close();
    outfile.close();
    return 0;
} The program is giving output as Problem 1: n = 7
Pmatrix:
0 0 0 6 3 0 6 
0 0 5 0 0 4 0 
0 5 0 0 0 4 5 
6 0 0 0 3 0 6 
3 0 0 3 0 4 0 
0 4 4 0 4 0 0 
6 0 5 6 0 0 0 

V1-Vj: shortest path and length
V1 : 0
V1 V2 : 6
V1 V3 : 5
V1 V4 V6 : 4
V1 V5 V3 : 6
V1 V6 : 3
V1 V7 V6 : 6
V2-Vj: shortest path and length
V2 V1 : 6
V2 : 0
V2 V3 V5 : 6
V2 V4 : 4
V2 V5 : 5
V2 V6 V4 : 5
V2 V7 : 3
V3-Vj: shortest path and length
V3 V1 : 5
V3 V2 V5 : 6
V3 : 0
V3 V4 : 3
V3 V5 : 1
V3 V6 V4 : 4
V3 V7 V5 : 6
V4-Vj: shortest path and length
V4 V1 V6 : 4
V4 V2 : 4
V4 V3 : 3
V4 : 0
V4 V5 V3 : 4
V4 V6 : 1
V4 V7 V6 : 4
V5-Vj: shortest path and length
V5 V1 V3 : 6
V5 V2 : 5
V5 V3 : 1
V5 V4 V3 : 4
V5 : 0
V5 V6 V4 V3 : 5
V5 V7 : 5
V6-Vj: shortest path and length
V6 V1 : 3
V6 V2 V4 : 5
V6 V3 V4 : 4
V6 V4 : 1
V6 V5 V4 : 5
V6 : 0
V6 V7 : 3
V7-Vj: shortest path and length
V7 V1 V6 : 6
V7 V2 : 3
V7 V3 V5 : 6
V7 V4 V6 : 4
V7 V5 : 5
V7 V6 : 3
V7 : 0
Problem 2: 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 : 0
V1 V2 : 1
V1 V3 : 2
V1 V4 : 1
V1 V5 V2 : 3
V1 V6 V2 : 4
V2-Vj: shortest path and length
V2 V1 : 1
V2 : 0
V2 V3 V1 : 3
V2 V4 V1 : 2
V2 V5 : 2
V2 V6 : 3
V3-Vj: shortest path and length
V3 V1 : 2
V3 V2 V1 : 3
V3 : 0
V3 V4 V1 : 3
V3 V5 : 3
V3 V6 V2 V1 : 6
V4-Vj: shortest path and length
V4 V1 : 1
V4 V2 V1 : 2
V4 V3 V1 : 3
V4 : 0
V4 V5 : 3
V4 V6 V2 V1 : 5
V5-Vj: shortest path and length
V5 V1 V2 : 3
V5 V2 : 2
V5 V3 : 3
V5 V4 : 3
V5 : 0
V5 V6 V2 : 5
V6-Vj: shortest path and length
V6 V1 V2 : 4
V6 V2 : 3
V6 V3 V2 : 6
V6 V4 V2 : 5
V6 V5 V2 : 5
V6 : 0
The output should be like 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