Currently working on a vjudge exercise and I'm having issues figuring out what's the problem with my implementation of the exercise.
Problem summary:
Given a directed graph with n nodes (where n is at most 500), an adjacency matrix of all the distances between them, and a list of n nodes that defines the order to remove nodes from this graph, perform the following process:
Iterate through the list of nodes to remove. At each stage, add the sum of the shortest distances between each ordered pair of distinct non-removed nodes in the graph to the answer (which starts as 0). Then, remove the current node in the list from the graph, which can change the shortest distances for later iterations. At the end, output the answer.
Full problem statement:
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)
#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.
The issue with your code is that you run Floyd–Warshall only once and do not handle removing nodes properly. When a node is destroyed, you only ignore paths that start or end at the node, without considering the fact that the shortest path between other pairs of nodes might have already used an edge that goes through the destroyed node. In fact, the only way to handle removing a node is to rebuild the entire shortest paths matrix, which is too slow to do every time.
Instead, notice that the order of performing operations implied by the problem statement misleads you towards an inefficient solution. If you go through the destroyed nodes in reverse, then each time you are adding a new node to the graph rather than destroying a node, so the update of shortest paths can be done in O(N^2).
Here is a working solution:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int t, n;
for (std::cin >> t; t--;) {
std::cin >> n;
std::vector<std::vector<int>> cost(n, std::vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
std::cin >> cost[i][j];
std::vector<int> order(n);
for (int& o : order) std::cin >> o;
long long totalPower = 0;
std::vector<bool> active(n);
for (int i = n - 1; i >= 0; --i) {
active[order[i]] = true;
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k) {
cost[j][k] = std::min(cost[j][k], cost[j][order[i]] + cost[order[i]][k]);
if (active[j] && active[k]) totalPower += cost[j][k];
}
}
std::cout << totalPower << '\n';
}
}