Pagini recente » Cod sursa (job #2277751) | Cod sursa (job #2828988)
#include <fstream>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f("cablaj.in");
ofstream g("cablaj.out");
#define NMAX 3005
int n;
bool viz[NMAX];
double sol, dist_min[NMAX];
pair<int, int> localitati[NMAX];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> q;
void citire() {
f >> n;
for (int i = 1; i <= n; ++i)
f >> localitati[i].first >> localitati[i].second;
}
double distanta(int x, int y) {
return sqrt((double) (localitati[x].first - localitati[y].first) * (localitati[x].first - localitati[y].first) +
(localitati[x].second - localitati[y].second) * (localitati[x].second - localitati[y].second));
}
void initializare() {
dist_min[1] = 0;
viz[1] = true;
for (int i = 2; i <= n; i++) {
dist_min[i] = distanta(1, i);
q.push({dist_min[i], i});
}
}
void actualizare_distante(int nod) {
for (int i = 2; i <= n; i++)
if (!viz[i])
if (distanta(nod, i) < dist_min[i]) {
dist_min[i] = distanta(nod, i);
q.push({dist_min[i], i});
}
}
void prelucrare() {
while (!q.empty()) {
pair<double, int> muchie = q.top();
q.pop();
if (viz[muchie.second])
continue;
viz[muchie.second] = true;
sol += muchie.first;
actualizare_distante(muchie.second);
}
}
int main() {
citire();
initializare();
prelucrare();
g << fixed << setprecision(3) << sol;
return 0;
}