poj 2349 Arctic Network（prime）

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 510

const double M=1e12;//定义一个大值  
int p,s;

struct dot //哨站结点 
{
	double x,y;
}d[N];

double map[N][N];
double rank[N],dst[N];//rank放最小生成树的各边长，dst放各点到MST的最近距离 
int vis[N];

double dist(int i,int j)//求两点距离 
{
	double x,y;
	x=d[i].x-d[j].x;
	y=d[i].y-d[j].y;
	
	return sqrt(x*x+y*y);
}

void init()
{
	int i,j;
	
	memset(map,0,sizeof(M));
	for (i=0;i<p;i++)//初始化图 
	{
		for (j=0;j<p;j++)
		{
			if (i==j)
			{
				map[i][j]=0;
			}
			
			else
			{
				map[i][j]=map[j][i]=dist(i,j);
			}
		}
	}
	
	memset(vis,0,sizeof(vis));
	memset(dst,0,sizeof(dst));
}

//bool cmp(int i,int j)
//{
//	if (rank[i]<rank[j])
//	{
//		return true;
//	}
//	return false;
//}

void findans()
{
	int i,j;
	sort(rank,rank+p-1);//按增序排列,注意排序范围为rank+p-1,因为MST只有p-1条边 
	printf("%.2f\n",rank[p-s-1]);// （p-1）-(s-1)-1,因为序号从0开始 
	
//	for (i=0;i<p;i++)
//	{
//		for (j=0;j<p;j++)
//		{
//			printf("%10.2f",map[i][j]);
//		}
//		printf("\n");
//	}
//	printf("\n");
//	for (i=0;i<p-1;i++)
//	{
//		printf("%10.2f",rank[i]);
//	}
}

void prime()
{
	int cnt=0,k,j,point,i;
	double min;
	
	vis[0]=1;//把0点放入MST 
	for (i=0;i<p;i++)//初始化dst 
	{
		dst[i]=map[i][0];
	}
	
	for (i=1;i<p;i++)//找距MST最近的点 
	{
		min=M;
		for (j=0;j<p;j++)
		{
			if (vis[j]==0&&min>dst[j])
			{
				min=dst[j];
				point=j;
			}
		}
		
//		if (min==M)
//		{
//			break;
//		}
		
		vis[point]=1;
		rank[cnt++]=min;
		
		for (k=0;k<p;k++)//更新各点到MST的最小距离 
		{
			if (vis[k]==0&&dst[k]>map[k][point])
			{
				dst[k]=map[k][point];
			}
		}
	}
	findans();
}

int main()
{
	int i,n,j;
	double x,y;
	
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d%d",&s,&p);
		
		for (j=0;j<p;j++)
		{
			scanf("%lf%lf",&d[j].x,&d[j].y);
		}
		
		init();
		prime();
	}
	
	return 0;
}