Source Code

Problem: 2349  User: yzhw 
Memory: 2120K  Time: 16MS 
Language: C  Result: Accepted 

Source Code 
# include <stdio.h>
# include <string.h>
# include <math.h>
struct
{
	int x,y;
}point[501];
double len[501][501];
int s,n;
void prim(double length[])
{
	int c=0,i;
	double data[501];
	int used[501];
	memset(used,0,sizeof(used));
	used[1]=1;
	for(i=2;i<=n;i++) data[i]=len[1][i];
	for(i=1;i<n;i++)
	{
		int j,res=0;
		double min=9999999;
		for(j=1;j<=n;j++)
			if(!used[j]&&data[j]<min)
				min=data[j],res=j;
		length[++c]=min;
                used[res]=1;
		for(j=1;j<=n;j++)
			if(!used[j]&&len[res][j]<data[j])
				data[j]=len[res][j];
	}
}
int cmp(const void *a,const void *b)
{
    double aa=*(double *)a;
    double bb=*(double *)b;
    if(fabs(aa-bb)<1e-5) return 0;
    else if(aa-bb>0) return -1;
    else return 1;
}
int main()
{
	int testcase;
	scanf("%d",&testcase);
	while(testcase--)
	{
		int i,j;
                double length[501];
		scanf("%d %d",&s,&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&point[i].x,&point[i].y);
		}
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
				len[i][j]=len[j][i]=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
		
		prim(length);
		qsort(length+1,n-1,sizeof(double),cmp);
		printf("%.2f\n",length[s]);
	}
}