一个状压dp模板题。
那么问题来了，为什么要进行状态压缩呢？
其实道理很简单，如果不进行压缩的话，dp数组需要写成dp2...2
最高需要MAXN+1维，这显然是我们所不能够接受的。
但是我们观察，每一维其实也就两个状态，即取与不取，这与我们的二进制开关性很像。
于是我们将20维状态压缩到一个20位的二进制数，即每一位代表状态取与不取。
dp方程为$$dp[i][j] = min(dp[i][j],dp[i去除j][k] + G[j][k]);$$
dp数组即在j点经过i里面保存的点的状态
下面给出参考代码：

#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<c;++a)
#define MAXN 20
using namespace std;

int n,ans;
int G[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    f(i,0,n)
        f(j,0,n) 
            cin >> G[i][j];

    memset(dp,0x3F3F3F,sizeof(dp));

    dp[1][0] = 0;
    for(int i = 1; i <= (1 << n) - 1; ++i)
        f(j,0,n)
            if((i >> j) & 1)
                f(k,0,n)
                    dp[i][j] = min(dp[i][j],dp[i ^ (1 << j)][k] + G[j][k]);

    cout << dp[(1 << n) - 1][n - 1] << endl;

    return 0;
}

对几个小细节进行解释：

• 首先dp数组需要初始化成最大值
• 在进行状态转移之前需要判断第j位是否已经被选择，即（(i >> j) & 1）是否为真
• （i ^ (1 << j)）即取上一层状态（将第j位异或成0）