hdu 1162

#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 ",dis);
}
return 0;
}

原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410934.html