描述:水题,就不解释了…… #include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; double count; int n,step[10]; void dfs(int cur,double sum,int *flag,int (*p)[10]) { if(cur>n) { if(sum<count) { count=sum; for(int i=1; i<=n; i++) step[i]=flag[i]; } return; } else for(int i=1; i<=n; i++) { int j; for( j=1; j<=n; j++) if(flag[j]==i) break; if(flag[j]==i) continue; flag[cur]=i; if(cur>=2) { int x=p[0][flag[cur-1]],y=p[1][flag[cur-1]]; double c=sqrt((p[0][i]-x)*(p[0][i]-x)+(p[1][i]-y)*(p[1][i]-y)); dfs(cur+1,sum+c,flag,p); } else dfs(cur+1,sum,flag,p); flag[cur]=0; } } int main() { #ifndef ONLINE_JUDGE freopen("a.txt","r",stdin); #endif int j(0),num[2][10],flag[10]; while(scanf("%d",&n)!=EOF) { if(!n) break; memset(num,0,sizeof(num)); memset(flag,0,sizeof(flag)); printf("**********************************************************\n"); printf("Network #%d\n",++j); count=100000; for(int i=1; i<=n; i++) scanf("%d%d",&num[0][i],&num[1][i]); dfs(1,0,flag,num); for(int i=1; i<n; i++) { int x1=num[0][step[i]],y1=num[1][step[i]],x2=num[0][step[i+1]],y2=num[1][step[i+1]]; printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n",x1,y1,x2,y2,sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16); } printf("Number of feet of cable required is %.2lf.\n",count+(n-1)*16); } return 0; }