题目描述

房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。

输入输出格式

输入格式：

 

第一行一个数n (n<=15)

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

 

输出格式：

 

一个数，表示要跑的最少距离，保留2位小数。

 

输入输出样例

输入样例#1：

41 11 -1-1 1-1 -1

输出样例#1：

7.41

 

这题开始用搜索做的，稍微剪下枝就能水过去，不过时间用的比较多，后来用 DP 做了一遍。

用二进制表示一个集合，比如  1011 表示一个包含了 0,1,3 结点的集合。

dp[i][j] 表示，在 i 集合中，以 j 结点作为起始点走完集合中所有点的最短路径。

dp[i][j] = min(dp[k][x] + len[j][x])

k 是去掉 j 结点的集合，x 是 k 中的任意一点， len[j][x] 表示 j 到 x 的距离。

 

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAX = 17;const int INF = 0x3fffffff;double dp[1<
        
          0){            //如果 i 结合有第 j 个结点                 int k = i - t;            //k 集合等于 i 集合去掉 j 结点//                if(i == 3){//                    cout << k << endl;//                }                for(int x=0; x<=n; x++){                    t = (1<
         
           0){    //如果 k 集合里有第 x 个结点                         //dp[k][x] + len[x][j] ： 从 j 点出发到 x 点的距离再加上从 x 出发走完 k 集合的最短距离                         dp[i][j] = min(dp[i][j], dp[k][x] + len[j][x]);                    }                }             }        }    }        ans = dp[((1<<(n+1))-1)][0];    printf("%.2lf", ans);        return 0;}