题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4463
很裸的一道题目，稍微处理一下输入即可
代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 60
int n;
double sumweight;
int tol;
int cnt;
int p,q;
class node
{
public:
int from;
int to;
double w;
};
class point
{
public:
int x;
int y;
};
point address[maxn];
node edge[maxn*maxn];
int parent[maxn*maxn];
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void addEdge(int u,int v)
{
edge[tol].from=u;
edge[tol].to=v;
edge[tol].w=dis(address[u],address[v]);
if((u==p && v==q)||(u==q && v==p))
edge[tol].w=;
tol++;
}
void UFset()
{
for(int i=;i<maxn*maxn;i++)
parent[i]=-;
}
int Find(int x)
{
int s;
for(s=x;parent[s]>=;s=parent[s]);//我总是把parent[s]>=0 写为s>=0;
while(s!=x)
{
int tmp=parent[x];
parent[x]=s;
x=tmp;
} return s;
}
void Union(int u,int v)
{
int r1=Find(u);
int r2=Find(v);
int tmp=parent[r1]+parent[r2];
if(parent[r1]>parent[r2])
{
parent[r1]=r2;
parent[r2]=tmp;
}
else
{
parent[r2]=r1;
parent[r1]=tmp;
}
}
bool cmp(node a ,node b)
{
return a.w < b.w;
}
void Kruskal()
{
int u,v;
UFset();
cnt=;
for(int i=;i<tol;i++)
{
u=edge[i].from;
v=edge[i].to;
if(Find(u)!= Find(v))
{
sumweight+=edge[i].w;
cnt++;
Union(u,v);
if(cnt==n-) break;
}
} }
int main()
{
while(scanf("%d",&n)&&n)
{
tol=; scanf("%d%d",&p,&q);
int x,y;
for(int i=;i<=n;i++)
{
scanf("%d%d",&x,&y);
address[i].x=x;
address[i].y=y;
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
addEdge(i,j);
}
sumweight=dis(address[p],address[q]);
sort(edge,edge+tol,cmp);
Kruskal();
printf("%.2f\n",sumweight); } return ;
}