#include <iostream>
#include <vector>
#include <string>
#include <iomanip>

using namespace std;

const int INF = 999999;

int main() {
    int N;

    cout << "Enter number of routers: ";
    cin >> N;

    vector<vector<int>> cost(N, vector<int>(N));
    vector<vector<int>> distance(N, vector<int>(N));
    vector<vector<int>> nextHop(N, vector<int>(N, -1));

    cout << "\nEnter the network cost matrix:\n";
    cout << "Enter -1 for INF (not directly connected)\n";

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> cost[i][j];

            if (cost[i][j] == -1)
                cost[i][j] = INF;

            distance[i][j] = cost[i][j];

            if (i == j) {
                distance[i][j] = 0;
                nextHop[i][j] = i;
            }
            else if (cost[i][j] != INF) {
                nextHop[i][j] = j;
            }
        }
    }

    cout << "\nInitial Cost Matrix:\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (cost[i][j] == INF)
                cout << "INF ";
            else
                cout << cost[i][j] << " ";
        }
        cout << endl;
    }

    cout << "\nInitial Routing Tables:\n";

    for (int i = 0; i < N; i++) {
        cout << "\nRouter " << i << ":\n";
        cout << "Destination\tCost\tNext Hop\n";

        for (int j = 0; j < N; j++) {
            cout << j << "\t\t";

            if (distance[i][j] == INF)
                cout << "INF\t";
            else
                cout << distance[i][j] << "\t";

            if (nextHop[i][j] == -1)
                cout << "-";
            else
                cout << nextHop[i][j];

            cout << endl;
        }
    }

    bool updated;

    do {
        updated = false;

        for (int source = 0; source < N; source++) {
            for (int destination = 0; destination < N; destination++) {
                for (int neighbour = 0; neighbour < N; neighbour++) {

                    if (cost[source][neighbour] != INF &&
                        distance[neighbour][destination] != INF) {

                        int newCost =
                            cost[source][neighbour] +
                            distance[neighbour][destination];

                        if (newCost < distance[source][destination]) {
                            distance[source][destination] = newCost;
                            nextHop[source][destination] = neighbour;
                            updated = true;
                        }
                    }
                }
            }
        }

    } while (updated);

    cout << "\nFinal Routing Tables:\n";

    for (int source = 0; source < N; source++) {
        cout << "\nRouting Table for Router " << source << ":\n";
        cout << "Destination\tCost\tNext Hop\n";

        for (int destination = 0; destination < N; destination++) {
            cout << destination << "\t\t";

            if (distance[source][destination] == INF)
                cout << "INF\t";
            else
                cout << distance[source][destination] << "\t";

            if (nextHop[source][destination] == -1)
                cout << "-";
            else
                cout << nextHop[source][destination];

            cout << endl;
        }
    }

    int selectedSource, selectedDestination;

    cout << "\nEnter source router: ";
    cin >> selectedSource;

    cout << "Enter destination router: ";
    cin >> selectedDestination;

    if (distance[selectedSource][selectedDestination] == INF) {
        cout << "No path exists between the selected routers.\n";
    }
    else {
        cout << "\nMinimum Cost: "
             << distance[selectedSource][selectedDestination] << endl;

        cout << "Shortest Path: ";

        int current = selectedSource;
        cout << current;

        while (current != selectedDestination) {
            current = nextHop[current][selectedDestination];

            if (current == -1) {
                cout << "\nPath cannot be determined.";
                return 0;
            }

            cout << " -> " << current;
        }

        cout << endl;
    }

    return 0;
}