Faccio WA in almeno meta’ dei casi tranne che il primo (N=2) che lo fullo.
Ho gia’ provato a testare in locale con un grader che genera risultati e li prova contro una solve con dijkstra ma non trova nulla di sbagliato.
Grazie in anticipo!
/*
* This template is valid both in C and in C++,
* so you can expand it with code from both languages.
*/
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
// constraints
#define MAXN 3000
#define pii pair<int, int>
#define pipii pair<int, pii>
using namespace std;
// input data
int get_cost(int x1, int y1, int x2, int y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
int main() {
// uncomment the following lines if you want to read/write from files
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int N;
cin >> N;
// insert your code here
vector<pii> towers;
char buf;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> buf;
if (buf == 'T') {
towers.push_back({i,j});
}
}
}
int M = towers.size();
int cost = 0;
vector<pii> dist(M, {INT_MAX, 0});
set<int> left;
for (int i = 0; i < M; i++) left.insert(i);
dist[0] = {0,0};
while (!left.empty()) {
int curr = *left.begin();
for (auto nxt : left) {
if (dist[nxt] < dist[curr]) curr = nxt;
}
left.erase(curr);
for (int nxt = 0; nxt < M; nxt++) {
if (curr == nxt) continue;
int w = get_cost(towers[curr].first, towers[curr].second, towers[nxt].first, towers[nxt].second);
if (dist[nxt].first > dist[curr].first + w || (dist[nxt].first == dist[curr].first + w && w < dist[nxt].second)) {
cost = cost + w - dist[nxt].second;
dist[nxt].first = dist[curr].first + w;
dist[nxt].second = w;
}
}
}
cout << cost << endl; // print the result
return 0;
}