PersonalCorpus 版 (精华区)

40248 2002-10-09 21:26:39 Accepted
1203 C++ 00:00.01 480K Big Guava


double dl[100][100];
bool used[100];
bool v[100][100];

double func3(int n)
{
    int i,j,k,best_j,best_k;
    double best,res=0;

    for (i=1;i<n;i++) {
        best=100000000;
        for (j=0;j<n;j++) if (used[j])
            for (k=1;k<n;k++) if (!used[k])
                if (best>dl[j][k]) {
                    best=dl[j][k];
                    best_j=j;
                    best_k=k;
                }
        used[best_k]=true;
        v[best_j][best_k]=true;
        v[best_k][best_j]=true;
        res+=best;
    }
    return res;
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1203","r",stdin);
    freopen("c:\\0acm\\zju\\o1203","w",stdout);
#endif

    int i,j,k,n,t=0;
    double p[100][2];

    while (1) {
        scanf("%d\n",&n);
        if (n==0) break; else t++;
        if (t>1) printf("\n");
        for (i=0;i<n;i++) scanf("%lf%lf\n",&p[i][0],&p[i][1]);
        for (i=0;i<n;i++) for (j=i;j<n;j++) {
                dl[i][j]=sqrt((p[i][0]-p[j][0])*(p[i][0]-p[j][0])+
                                (p[i][1]-p[j][1])*(p[i][1]-p[j][1]));
                dl[j][i]=dl[i][j];
        }
        memset(used,0,sizeof(used));
        memset(v,0,sizeof(v));
        used[0]=true;

        printf("Case #%d:\n",t);
        printf("The minimal distance is: %.2lf\n",func3(n));
    }
}