> 
> /*
>  *Descripttion: 2349 Arctic Network
>  *				It seems that this problem is a MST problem
>  *More :	Prim algorithm
>  *Author : BlueBlood --	RTFSC
>  *Time: 2005 - 12- 09
>  */
> 
> #include <iostream>
> #include <cstdlib>
> #include <cstdlib>
> #include <algorithm>
> #include <cmath>
> 
> using namespace std;
> 
> #define MAXWEIGHT 32767
> 
> typedef struct{
> 	int vi;		//head of a edge
> 	int vj;		//tail of a edge
> 	double weight;	
> } edge;
> 
> int s;
> int p;
> double d;
> int * x;
> int * y;
> double ** adj;
> double *res;
> edge *T;
> 
> void Prim( void )
> {
> 	int m;
> 	int v;
> 	int nmin;
> 	double dis;
> 
> 	edge e;
> 
> 	//Initializing T;
> 	for (int j = 1; j < p; j++)
> 	{
> 		T[j-1].vi = 1;
> 		T[j-1].vj = j + 1;
> 		T[j-1].weight = adj[0][j];
> 	}
> 
> 	//find out the k+1 th MST's edge
> 	for (int k = 0; k < p - 1; k++)
> 	{
> 		nmin = MAXWEIGHT;
> 
> 		//find the edge with the smallest weight from T[k],..., T[n-2] to join the MST;
> 		for (j = k; j < p - 1; j++)
> 		{
> 			if (T[j].weight < nmin)
> 			{
> 				nmin = T[j].weight;
> 				m = j;
> 			}
> 		}
> 		
> 
> 		//Exchange T[m] & T[k];
> 		e = T[m]; 
> 		T[m] = T[k];
> 		T[k] = e;
> 
> 		//v is the number of the vertex newly added to MST
> 		v = T[k].vj;
> 
> 		//Modify T[k + 1], T[k + 2],..., T[n - 1];
> 		for (j = k + 1; j < p - 1; j++)
> 		{
> 			dis = adj[v-1][T[j].vj - 1];
> 
> 			if ( d < T[j].weight)
> 			{
> 				T[j].weight = dis;
> 				T[j].vi  = v;
> 			}
> 		}
> 
> 	}
> }
> 
> int main()
> {
> 	int testCase;
> 	int i;
> 	int j;
> 	int k;
> 	
> 	cin >> testCase;
> 
> 	for ( i = 0;  i < testCase; i++)
> 	{
> 		cin >> s >> p;
> 
> 		x = new int [p];
> 		y = new int [p];
> 		adj = new double * [p];
> 		res = new double [p];
> 		T = new edge [p];
> 
> 		for (j = 0; j < p; j++)
> 		{
> 			cin >> x[j] >> y[j];
> 			adj[j] = new double [p];
> 		}
> 
> 		for (j = 0; j < p; j++)
> 			for (k = 0; k < p; k++)
> 			{
> 				if (k == j)
> 					adj[j][k] = MAXWEIGHT;
> 				else
> 					adj[j][k] = sqrt( (x[j] - x[k])*(x[j] - x[k]) + (y[j] - y[k])*(y[j] - y[k]));
> 			}
> 
> 
> 		Prim();
> 
> 		for ( i = 0; i < p - 1 ; i++)
> 		{
> 			res[i] = T[i].weight;
> 		}
> 
> 		sort(&res[0], & res[p-1]);
> 
> 		printf("%.2f\n",res[p-1-s]);
> 
> 	}
> 
> 	system("pause");
> 	return 0;
> }