Cod sursa(job #2123806)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 6 februarie 2018 17:29:07
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#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;
}