【刷题】动态规划——状态压缩DP（集合类）：毕业旅行问题 （字节跳动2019春招研发）

【刷题】动态规划——状态压缩DP（集合类）：毕业旅行问题 （字节跳动2019春招研发）

题目链接

和最短Hamilton路径基本完全一致。不同的是这题最后要回到起点。
最后枚举从第i个点回到起点找到最小的就是答案，即f[111...111, i] + w[i][1]

这题C语言内存限制的有点不科学，f用二维数组会超内存，开了vector才勉强过。

#include 
#include 
#include 
#include 
using namespace std;
int n, w[20][20];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < n; j ++) {
            scanf("%d", &w[i][j]);
        }
    }
    vector< vector > f(1 << n, vector(n, 0x3f3f3f3f));
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            if (i >> j & 1) {// 状态i含有j
                for (int k = 0; k < n; k ++ ) {
                    int state_k = i - (1 << j); // 状态i去掉j，得到state_k
                    if (state_k >> k & 1) {// state_k含有k
                        f[i][j] = min(f[i][j], f[state_k][k] + w[k][j]);
                    }
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i < n; i ++ ) {
        ans = min(ans, f[(1 << n) - 1][i] + w[i][0]);
    }
    printf("%dn", ans);
    return 0;
}