Hdu4463

May 30, 2021


题链接: 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;
}