I’m having issues finding the problem with the following implementation of Floyd-Warshall APSP Algorithm.

Currently working on a vjudge exercise and I’m having issues figuring out what’s the problem with my implementation of the exercise. For matrices n < 4 I’m having no issues, but my problem arises with matrices such that n >= 4.

My take is that the first loop, on the one hand, is not necessary given that I already have the cost matrix of the graph. Secondly, it might be the responsible for my wrong output.

Here’s the link to the exercise: Geonosis (UVA-13211)

#include <iostream>
#include <vector>
#include <limits>

using namespace std;
const int INFTY = numeric_limits<int>::max(); // Use numeric_limits for infinity

// Graph representing the Geonosis Map.
struct Graph {
    vector<vector<int>> costo;

    explicit Graph(int n) {
        costo.resize(n, vector<int>(n));
    }
};

// Floyd-Warshall implementation APSP.
void APSP(const Graph& geonosis, vector<vector<int>>& dist) { // Pass dist by reference (improves space complexity)
    unsigned long n = geonosis.costo.size();

    // Initialize dist with the given graph's costo
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                dist[i][j] = 0;
            } else if (geonosis.costo[i][j] != 0) {
                dist[i][j] = geonosis.costo[i][j];
            }
        }
    }

    // Compute all pair shortest paths using 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 (geonosis.costo[i][k] != INFTY && geonosis.costo[k][j] != INFTY) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

            }
        }
    }
}

int solve(int t) {
    while (t--) {
        int n;
        unsigned long long res = 0;
        cin >> n;
        cin.ignore();  // to ignore the newline after the number.

        // to create my case matrix and return the shortest path to destroy all towers.
        Graph geonosis(n);
        vector<int> destOrder(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> geonosis.costo[i][j];
            }
        }

        // we make a sequence that stores the dest. order for the case.
        for (int i = 0; i < n; ++i) {
            cin >> destOrder[i];
        }

        vector<vector<int>> dist(n, vector<int>(n, INFTY));

        APSP(geonosis, dist);
        // once we finish executing APSP, dist matrix has the shortest path from each vertex i to each vertex j while i != j.
        // we want to keep track of the towers that have been destroyed
        vector<bool> destroyed(n, false);

        for (int d = 0; d < n; ++d) {
            int currentTower = destOrder[d];

            unsigned long long currentSum = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (!destroyed[i] && !destroyed[j] && dist[i][j] != INFTY) {
                        currentSum += dist[i][j];
                    }
                }
            }

            destroyed[currentTower] = true;
            // Add the current sum to the total sum
            res += currentSum;
        }

        // Print the total sum of all shortest paths
        cout << res << endl;
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    solve(t);
    return 0;
}

I have tried implementing the exercise with a Dantzig’s algorithm approach to calculate APSP, but it’s still providing the same output. I can’t even debug with cLion where the possible error might be.