hdu 1162

时间:2024-12-01 20:36:37

#include<stdio.h>

#include<string.h>

#include<math.h>

#define N 200

#define inf 999999999

double map[N][N];

int visit[N],next[N];

int main() {

int n,m,i,j,k,cnt;

double a[N],b[N],dis,min;

while(scanf("%d",&n)!=EOF) {

for(i=1;i<=n;i++)

scanf("%lf%lf",&a[i],&b[i]);

for(i=1;i<n;i++)

for(j=i+1;j<=n;j++)

map[i][j]=map[j][i]=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));

memset(visit,0,sizeof(visit));

visit[1]=1;

next[0]=1;

cnt=1;dis=0;

while(cnt!=n) {

min=inf;

for(i=0;i<cnt;i++) 

for(j=1;j<=n;j++)

if(visit[j]==0&&map[next[i]][j]<min) {

min=map[next[i]][j];

next[cnt]=j;

}

dis+=min;

visit[next[cnt]]=1;

cnt++;

}

printf("%.2f\n",dis);

}

return 0;

}