Cod sursa(job #534833)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 16 februarie 2011 12:16:07
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;

#define N_MAX 3003
#define fs first
#define sc second
typedef pair <float,float> p;
typedef pair <int,int> pp;

p xy[N_MAX];

int nrMuchii;

int n,i,j;

float rez;

float dist(p a,p b)
{
	return sqrtf( (a.fs-b.fs)*(a.fs-b.fs)+(a.sc-b.sc)*(a.sc-b.sc) );
}

float cost[N_MAX];
bool inArb[N_MAX];

int main()
{
	freopen("cablaj.in","r",stdin);
	freopen("cablaj.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
		scanf("%f%f",&xy[i].fs,&xy[i].sc);
	
	inArb[1]=1;
	for(i=2;i<=n;i++)
	{
		cost[i]=dist( xy[1],xy[i] );
	}
	
	for(i=1;i<n;i++)
	{
		int nd=1;
		float Min=(1<<20);
		for(j=1;j<=n;j++)
		{
			if(inArb[j])
				continue;
			if(cost[j]<Min)
			{
				Min=cost[j];
				nd=j;
			}
		}
		
		//rez+=cost[nd];
		inArb[nd]=1;
		
		for(j=1;j<=n;j++)
		{
			if(j==nd)
				continue;
			if(inArb[j])
				continue;
			
			if(dist( xy[nd],xy[j] )<cost[j])
			{
				cost[j]=dist( xy[nd],xy[j] );
			}
		}
	}
	
	for(i=2;i<=n;i++)
		rez+=cost[i];
	
	printf("%f\n",rez);
	
	return 0;
}