P1433 吃奶酪

· · 题解 

/*这道题是一道经典的状压DP我们设dp[i][j] 为 当前吃了i块奶酪，现在在第j块奶酪的位置，所需要的最短路 */
//我们把二进制编码全都初始化为0 即000000
//每吃过一个奶酪就把一位上的0改成1，即000001，再把i改成j，代表现在在j这个点 
// 最后遍历一遍当所有奶酪都吃了的时候，最短路是多少就行了 

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

struct qq{

    double x,y;//因为坐标有可能是小数，所以用double存储 

}d[N];//d数组存第i个点的横纵坐标 

int n;
double dp[100001][1001],dis[10001][10001],ans = 1e9;//dp是动归数组，dis是一个矩阵，存的是i->j的距离 

int main () {

    scanf("%d",&n);//输入n 

    for (int i = 0;i <= (1 << n) - 1;i ++) {//我们把前面的全部初始化成为一个极大值，方便后面找小值 
        for (int j = 0;j <= 500;j ++) {
            dp[i][j] = 1e9; 
        }
    }

    d[0].x = 0.0;//注意起始点是 （0，0） 
    d[0].y = 0.0;

    for (int i = 1;i <= n;i ++) {
//      double x,y;
        scanf ("%lf%lf",&d[i].x,&d[i].y);//输入每个奶酪的坐标 
//      cout << d[i].x << d[i].y << ' ';
    }

    for (int i = 0;i <= n;i ++) {//求出dis矩阵，即i->j的距离 
        for (int j = 0;j <= n;j ++) {
            dis[i][j] = sqrt ((d[i].x - d[j].x) * (d[i].x - d[j].x) + (d[i].y - d[j].y) * (d[i].y - d[j].y)) * 1.0;
    //      cout << dis[i][j] << ' ';
        }
    }

    dp[0][0] = 0.0;//把边界设置一下，吃零块奶酪，且最后还在起点的距离为零 

    for (int bit = 0;bit <= (1 << n) - 1;bit ++) {
        for (int i = 0;i <= n;i ++) {
            if (dp[bit][i] == 1e9) continue;//判断这个点是不是没走过，没走过就说明对答案没有影响，直接弹掉就行 
            for (int j = 1;j <= n;j ++) {
                if ((bit & (1 << (j - 1)))) continue;//当这个二进制编码的位置不是0是，代表已经走过了，弹掉就行。 
            //  cout << dp[bit | (1 << (j - 1))][i] << ' ';
                if (dp[bit | (1 << (j - 1))][j] > dp[bit][i] + dis[i][j]) {//如果吃掉这个奶酪的最短路比之前更优的话，更新答案 
                    dp[bit | (1 << (j - 1))][j] = dp[bit][i] * 1.0 + dis[i][j] * 1.0;
            //      cout << dp[bit][j] << ' ';
                }
            }
        }
    }

    int bit = (1 << n) - 1;//注意，2的n次方是 10000（后面n个0）
    //而2的n - 1次方是 11111(n - 1) 个1，代表全都找完了，所以是2的n次方减一 
    ans = 1e9;//记得设成极大值 

    for (int i = 0;i <= n;i ++) {
        ans = min (ans,dp[bit][i]);//枚举一边找最小值就ok了 
    }
    printf("%.2lf",ans);//输出答案 
    return 0;//华丽结束 
}