Cod sursa(job #647467)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 11 decembrie 2011 15:14:54
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <cmath>
#define nmax 2010
#define eps 0.000001

int n, m, heap[nmax], poz[nmax], l, u[nmax];
long long cx[nmax], cy[nmax], x[nmax], y[nmax];
double d[nmax], sol;

int main()
{
	freopen("retea2.in","r",stdin);
	freopen("retea2.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, j, nod;
	double c;
	for (i=1; i<=n; i++) scanf("%d %d", &cx[i], &cy[i]);
	for (i=1; i<=m; i++) scanf("%d %d", &x[i], &y[i]);
	for (i=1; i<=m; i++) d[i]=-2;
	for (i=1; i<=m; i++)
	{
		for (j=1; j<=n; j++)
		{
			c=(x[i]-cx[j])*(x[i]-cx[j])+(y[i]-cy[j])*(y[i]-cy[j]);
			c=sqrt(c);
			if (d[i]<-1 || c<d[i]) d[i]=c;
		}
	}
	for (i=1; i<=m; i++) 
	{
		c=-1;
		for (j=1; j<=m; j++)
			if (!u[j])
				if (c==-1 || d[j]<c) 
				{
					c=d[j]; 
					nod=j;
				}
		u[nod]=1;
		sol+=d[nod];
		for (j=1; j<=m; j++)
			if (!u[j])
			{
				c=(x[nod]-x[j])*(x[nod]-x[j])+(y[nod]-y[j])*(y[nod]-y[j]);
				c=sqrt(c);
				if (c+d[i]<d[j]) d[j]=c+d[i];
			}
	}
	printf("%.6lf\n",sol);
}