Untitled

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

void floydWarshall(int n, vector<vector<int>>& dist, vector<vector<int>>& next) {
    // Floyd-Warshall algorithm with path reconstruction
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];  // Store the intermediate node
                }
            }
        }
    }
}

// Function to reconstruct the shortest path from i to j
vector<int> reconstructPath(int i, int j, const vector<vector<int>>& next) {
    if (next[i][j] == -1) return {};  // No path exists
    vector<int> path = {i};
    while (i != j) {
        i = next[i][j];
        path.push_back(i);
    }
    return path;
}

int main() {
    int n, m;
    cout << "Enter the number of nodes: ";
    cin >> n;
    cout << "Enter the number of edges: ";
    cin >> m;

    vector<vector<int>> dist(n, vector<int>(n, INF));
    vector<vector<int>> next(n, vector<int>(n, -1));

    // Initialize distance and next matrices
    for (int i = 0; i < n; ++i) dist[i][i] = 0;

    cout << "Enter the edges (u, v, weight):\n";
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
        next[u][v] = v;
    }

    // Run Floyd-Warshall algorithm
    floydWarshall(n, dist, next);

    // Array to count how often each node is used as an intermediate node
    vector<int> midNodeCount(n, 0);

    // Reconstruct the paths and count intermediate nodes
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                vector<int> path = reconstructPath(i, j, next);
                for (int k = 1; k < path.size() - 1; ++k) {
                    midNodeCount[path[k]]++;  // Count intermediate nodes (excluding start and end)
                }
            }
        }
    }

    // Find the most used intermediate node
    int mostUsedNode = -1;
    int maxCount = 0;
    for (int i = 0; i < n; ++i) {
        if (midNodeCount[i] > maxCount) {
            maxCount = midNodeCount[i];
            mostUsedNode = i;
        }
    }

    cout << "The most used intermediate node is: " << mostUsedNode << " used " << maxCount << " times.\n";
    return 0;
}