Cod sursa(job #2042125)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 18 octombrie 2017 08:48:22
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <cmath>
#define N_MAX 3005
#define inf (1 << 31) -1
#include <iomanip>
using namespace std;
ifstream f("cablaj.in");
ofstream g("cablaj.out");
struct punct
{
    int x;
    int y;
};
int n;
bool inApm[N_MAX];
double dist[N_MAX];
punct p[N_MAX];
double dist2Pct(punct p1, punct p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
void prim()
{
    int ok = 1, nod = 1;
    for(int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[1] = 0;
    inApm[1] = 1;
    double minn;
    while(ok)
    {
        ok = 0;
        minn = inf;
        for(int i = 1; i <= n; i++)
        {
            if(!inApm[i])
            {
                ok = 1;
                dist[i] = min(dist[i], dist2Pct(p[nod], p[i]));
                if(minn > dist[i])
                {
                    minn = dist[i];
                    nod = i;
                }
            }
        }
        inApm[nod] = 1;
    }
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        f >> p[i].x >> p[i].y;
    }
    prim();
    double s = 0;
    for(int i = 1; i <= n; i++)
        s += dist[i];
    g << fixed << setprecision(4) << s << "\n";
    return 0;
}