此题为暴力求解法回溯法的训练参考

 

翻译请戳

 

解题思路

回溯。

可以用数组存储中间路径，

如果链接完毕且小于最小值，将中间路径存入最终路径。

详见代码。

 

代码

#include
     
      #include
      
       #include
       
         const int maxLen = 10;typedef struct point {    int x, y;} Point;Point setP[maxLen];Point Path[maxLen];　　//存储“中间”路径Point Final[maxLen];  //存储“最终”路径bool connet[maxLen];int n;double min;double dist(Point A, Point B){    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}void Search(int start, int left, double res){    if(res>min) return ;    else if(left == 0) {         min = res;         for(int i=0; i
        
         0; i--) {            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n",               Final[i].x, Final[i].y, Final[i-1].x, Final[i-1].y, dist(Final[i], Final[i-1])+16.0);        }        printf("Number of feet of cable required is %.2lf.\n", min);        scanf("%d", &n);    }    return 0;}