类Prim算法求出最小生成树的每节最短距离。
然后，第s-1个最大的距离就是所求。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 10000000struct node
{int x,y;
}post[505];double g[505][505];
int vis[505];
double dist[505];
int mark[505];
int parent[505];
int n,s,p;double Distance(int i,int j)
{double s= ( post[i].x-post[j].x ) * ( post[i].x-post[j].x ) + ( post[i].y-post[j].y ) * ( post[i].y-post[j].y );return sqrt(s);
}int cmp(double a,double b)
{return a>b;
}int main()
{
// freopen("in.txt","r",stdin);scanf("%d",&n);while(n--){scanf("%d %d",&s,&p);for(int i=0;i<p;i++)scanf("%d %d",&post[i].x,&post[i].y);for(int i=0;i<p;i++)for(int j=i+1;j<p;j++){g[j][i]=Distance(i,j);g[i][j]=g[j][i];}for(int i=1;i<p;i++){dist[i]=g[0][i];vis[i]=0;parent[i]=0;}vis[0]=1;parent[0]=-1;for(int i=1;i<p;i++){int u;double m=INF;for(int j=1;j<p;j++)if( !vis[j] && dist[j]<m ){m=dist[j];u=j;}vis[u]=1;for(int j=1;j<p;j++)if( !vis[j] && dist[j]>g[u][j] ){dist[j]=g[u][j];parent[j]=u;}}dist[0]=0;sort(dist,dist+p,cmp);printf("%.2lf\n",dist[s-1]);}return 0;
}