S

#### str8

##### Guest

### 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.

After years of planning, the Galactic Empire has built the planetary fortress of Geonosis, a perfect prison for the leaders of the rebelion and a special place reserved for the evil Luke Skywalker. However, as it has been demonstrated with the failures of Death Star I and II, the fortress is not perfect and the evil Rebel Alliance plans to use a weakness detected in the communication towers surrounding Geonosis.

To achieve their evil plans, the Rebel Alliance has stolen a map with the structure of the fortress. Geonosis has a communication complex formed by n towers. Each pair of the complex’s tower is connected by power lines that send messages at a w cost of energy. The rebels want to build the Rogue Two ship to destroy the fortress and rescue its prisoners. To achieve that, they have to destroy all the towers of the fortress. They have discovered that the power necessary to destroy a tower is equal to the sum of the minimum energy needed to send messages between each pair of the fortress towers, either directly or indirectly through other towers.

Note that once a tower is destroyed, it stops counting for this formula.

On the other hand, the commander of the Rogue Two is very capricious so he wants to destroy the towers in a given order. Knowing the information of the communication towers in Geonosis and the order in which each tower will be destroyed, can you tell what is the power needed for the Rogue Two to complete it’s mission?

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)

Code:

```
#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 returning the same output. I can't even pinpoint the issue whilst debugging.