数据范围较小，暴力枚举全排列就行
//// main.cpp// uva216//// Created by Fangpin on 15/3/8.// Copyright (c) 2015年 FangPin. All rights reserved.//#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespace std;struct Point{int x,y;Point()=default;};double len(const Point &a,const Point &b){return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );}int main(int argc, const char * argv[]) {// insert code here…int n,ca=1;while(scanf("%d",&n),n){vector<Point> a;vector<int> b;vector<int> lis;for(int i=0;i<n;++i){Point tem;scanf("%d%d",&tem.x,&tem.y);a.push_back(tem);b.push_back(i);}double ans=0;lis=b;for(int i=0;i<a.size()-1;++i){ans+=len(a[i],a[i+1]);}while(next_permutation(b.begin(),b.end())){double tem=0;for(int i=0;i<a.size()-1;++i){tem+=len(a[b[i]],a[b[i+1]]);}if(tem<ans){ans=tem;lis=b;}}puts("**********************************************************");printf("Network #%d\n",ca++);for(int i=0;i<a.size()-1;++i){//printf( "Cable requirement to connect (%d,%d) to (%d,%d) is %lf feet.\n",a[lis[i]].x,a[lis[i]].y,a[lis[i+1]].x,a[lis[i+1]].y],len( a[lis[i]],a[lis[i+1]] ) );cout<<"Cable requirement to connect ("<<int(a[lis[i]].x)<<","<<int(a[lis[i]].y)<<") to ("<<int(a[lis[i+1]].x)<<","<<int(a[lis[i+1]].y)<<") is ";printf("%.2f",len(a[lis[i]],a[lis[i+1]])+16);cout<<" feet.\n";}cout<<"Number of feet of cable required is ";printf("%.2f.\n",ans+(n-1)*16);//puts("**********************************************************");}return 0;}
，刺是与生俱来的，上帝在赐予优越感同时捆-绑的附属品;
