1162.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 39 行

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
double a[101][101];
void main()
{
    int n,i_index;
    double x[101],y[101];
    double ants,min,len;
    int judge[101];
    int i,j,k,sign_k;
    while(cin>>n){
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(judge,0,sizeof(judge));
        for(i=0;i<n;i++)
            cin>>x[i]>>y[i];
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                a[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        len=0;judge[0]=1;
        for(i=0;i<n-1;i++){
            min=-1;
            for(j=0;j<n;j++)
                for(k=0;k<n;k++)
                    if(judge[j]==1&&judge[k]==0&&(min==-1||min>a[j][k])){
                        min=a[j][k];
                        sign_k=k;
                    }
            judge[sign_k]=1;
            len+=min;
        }
        printf("%.2lf\n",len);
    }
}