题链接: hdu-4463-Outlets
#include<bits/stdc++.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int n;
double g[N][N];
double dist[N];
bool st[N];
double x[510],y[510];
void prim(double a)
{
double res = 0.00;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;
if (i)
{
res += dist[t];
}
st[t] = true;
for (int j = 1; j <= n; j ++ )
{
dist[j] = min(dist[j], g[t][j]);
}
}
res+=a;
cout<<setiosflags(ios::fixed)<<setprecision(2)<<res<<endl;
}
int main()
{
while (cin >> n&&n)
{
for(int i=1;i<=n;i++){
dist[i]=INF;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=INF;
}
}
memset(st,false,sizeof st);
memset(x,0,sizeof x);
memset(y,0,sizeof y);
int p,q;
cin>>p>>q;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=g[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
double a=g[p][q];
g[p][q]=g[q][p]=0;
prim(a);
}
return 0;
}