本來以為這題是MST，但是題目要求的是每個node只能有兩條branch(想成是兩個連接點），也就是用一條線串起全部的node。 這題的input size最多只到8，所以就用暴力解，找出最佳的排列。
//ignore header files
struct point{
int x,y;
point(int _x,int _y){
x = _x;
y = _y;
}
};
#define dis(p1,p2) sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))
int main(int argc, char const* argv[])
{
int n;
int t = 0;
while(scanf("%d",&n) && n != 0){
int permutation[8] = {0,1,2,3,4,5,6,7};
vector<point> points;
for(int k = 0;k<n;k++){
int x,y;
scanf("%d %d",&x,&y);
points.push_back(point(x,y));
}
double min = 1e9;
int ans[8];
do{
double sum = 0;
for(int i = 0;i<n-1;i++){
sum = sum+dis(points[permutation[i]],points[permutation[i+1]]);;
}
if(sum<min){
for(int i = 0;i<n;i++)
ans[i] = permutation[i];
min = sum;
}
}while(next_permutation(permutation,permutation+n));
printf("**********************************************************\n");
printf("Network #%d\n",++t);
for(int i = 0;i<n-1;i++){
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n",points[ans[i]].x,points[ans[i]].y,points[ans[i+1]].x,points[ans[i+1]].y,dis(points[ans[i]],points[ans[i+1]])+16);
}
printf("Number of feet of cable required is %.2lf.\n",min+(n-1)*(16));
}
return 0;
}