Waterloo local 2002.09.28
/*********************************************
author : Grant Yuan
time : 2014.7.31
algorithm : Prim
source : POJ 2349
**********************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#define INF 0x3fffffff
#define MAX 507
using namespace std;
struct point{int x;int y;};
int t,n,p;
point v[MAX];
double cost[MAX][MAX];
bool used[MAX];
double mincost[MAX];
priority_queue<double>path;
void prim()
{
for(int i=1;i<=n;i++)
{
mincost[i]=INF;
used[i]=false;
}
mincost[1]=0;
for(int i=1;i<=n;i++)
{
double temp=INF;int k=1;
for(int j=1;j<=n;j++)
{
if(!used[j]&&mincost[j]<temp)
{
temp=mincost[j];
k=j;
}
}
path.push(temp);
used[k]=true;
for(int j=1;j<=n;j++)
{
mincost[j]=min(mincost[j],cost[k][j]);
}
}
}
int main()
{
scanf("%d",&t);
while(t--){
while(!path.empty())
path.pop();
scanf("%d%d",&p,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
cost[i][j]=INF;
cost[i][j]=cost[j][i]=sqrt(1.0*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1.0*(v[i].y-v[j].y)*(v[i].y-v[j].y));
}
prim();
for(int i=1;i<p;i++)
path.pop();
printf("%.2f\n",path.top());
}
return 0;
}
原文：http://blog.csdn.net/yuanchang_best/article/details/38318653