#include <iostream>
#include <iomanip>
using namespace std;

#define V 5
#define INF 99999

// Function to print matrix
void printMatrix(int matrix[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (matrix[i][j] == INF)
                cout << "INF ";
            else
                cout << setw(4) << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

// Floyd Warshall Algorithm
void floydWarshall(int W[V][V]) {
    int D[V][V], P[V][V];

    // Initialize D and P matrices
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            D[i][j] = W[i][j];
            if (i == j || W[i][j] == INF)
                P[i][j] = -1;
            else
                P[i][j] = i;
        }
    }

    // Floyd-Warshall Algorithm
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (D[i][k] != INF && D[k][j] != INF &&
                    D[i][k] + D[k][j] < D[i][j]) {

                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = P[k][j];
                }
            }
        }
    }

    // Print Distance Matrix
    cout << "\nShortest Distance Matrix (D):\n";
    printMatrix(D);

    // Print Path Matrix
    cout << "\nPredecessor Matrix (P):\n";
    printMatrix(P);

    // Function to print path
    auto printPath = [&](int start, int end) {
        if (P[start][end] == -1) {
            cout << "No path\n";
            return;
        }

        int path[V], count = 0;
        int v = end;

        while (v != start) {
            path[count++] = v;
            v = P[start][v];
        }
        path[count++] = start;

        cout << "Path: ";
        for (int i = count - 1; i >= 0; i--) {
            cout << path[i] + 1;
            if (i != 0) cout << " -> ";
        }
        cout << endl;
    };

    // Example paths
    cout << "\nExample Paths:\n";
    cout << "1 to 3: ";
    printPath(0, 2);

    cout << "3 to 2: ";
    printPath(2, 1);
}

int main() {
    // Input weight matrix based on given graph
    int W[V][V] = {
        {0,    3,    8,    2,   -4},
        {INF,  0,    4,  INF, INF},
        {INF, INF,   0,    1,   -5},
        {INF, INF, INF,    0,  INF},
        {INF,   7,  INF,   6,    0}
    };

    cout << "Initial Weight Matrix (W):\n";
    printMatrix(W);

    floydWarshall(W);

    return 0;
}