#include <stdio.h>
#include <string.h>
#include <math.h>
double road[1010][1010];
double dist[1010];
int visit[1010];
struct node
{
	double x,y;
};
struct node data[1010];
int main()
{
	int n,m,i,j,rec;
	double d,sum,max;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		scanf("%lf %lf",&data[i].x,&data[i].y);
		memset(road,0,sizeof(road));
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				d=sqrt((data[i].x-data[j].x)*(data[i].x-data[j].x)+(data[i].y-data[j].y)*(data[i].y-data[j].y));
				road[i][j]=d;
				road[j][i]=road[i][j];
			}
		}
		while(m--)
		{
			scanf("%d %d",&i,&j);
			road[i][j]=0;
			road[j][i]=0;
		}
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)
		dist[i]=road[1][i];
		visit[1]=1;
		sum=0.0;
		for(i=1;i<n;i++)
		{
			max=10000000.0;
			rec=-1;
			for(j=1;j<=n;j++)
				if(!visit[j]&&dist[j]<max)
				{
					max=dist[j];
					rec=j;
				}
				sum+=max;
				visit[rec]=1;
				for(j=1;j<=n;j++)
					if(!visit[j]&&road[rec][j]<dist[j])
						dist[j]=road[rec][j];
		}
		printf("%.2lf\n",sum);
	}
	return 1;
}



			

• Re:prime算法！付一下代码！仅供参考！！！ (24) sqc1999 2015-06-07 19:29:10