Pagini recente » Cod sursa (job #2719114) | Cod sursa (job #1965867) | Cod sursa (job #1746385) | Cod sursa (job #2121614) | Cod sursa (job #2123806)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define inf 0x3f3f3f
#define NMAX 1005
using namespace std;
int N;
double dist[NMAX];
bool viz[NMAX];
struct punct
{
double x, y;
}vPunct[NMAX];
vector <pair <int, double> >g[NMAX];
vector <pair <int, double> >::iterator it;
priority_queue <pair <double, int> > q;
double distPuncte(punct a, punct b)
{
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
void addPointToGraph(punct a, int nrPuncte)
{
dist[nrPuncte] = inf;
for(int i=1; i<=nrPuncte - 1; ++i)
{
double c = distPuncte(a, vPunct[i]);
g[nrPuncte].push_back(make_pair(i, c));
g[i].push_back(make_pair(nrPuncte, c));
}
}
void apmPrim()
{
q.push(make_pair(0, 1));
dist[1] = 0;
while(!q.empty())
{
int cost = -1 * q.top().first;
int nod = q.top().second;
q.pop();
viz[nod] = true;
for(it = g[nod].begin(); it != g[nod].end(); ++it)
if(viz[it->first] == false && dist[it->first] > it->second)
{
dist[it->first] = it->second;
q.push(make_pair(-1 * it->second, it->first));
}
}
}
void resetVectors(int nrPuncte)
{
for(int i=1; i<=nrPuncte; ++i)
{
dist[i] = inf;
viz[i] = false;
}
}
double calculareDistTotala(int nrPuncte)
{
double distTotala = 0;
for(int i=1; i<=nrPuncte; ++i)
distTotala += sqrt(dist[i]);
return distTotala;
}
void read()
{
scanf("%d", &N);
for(int i=1; i<=N; ++i)
{
scanf("%lf%lf", &vPunct[i].x, &vPunct[i].y);
addPointToGraph(vPunct[i], i);
resetVectors(i);
apmPrim();
printf("%.5lf\n", calculareDistTotala(i));
}
}
int main()
{
freopen("desen.in", "r", stdin);
freopen("desen.out", "w", stdout);
read();
return 0;
}