16.最短Hamilton路径 状态压缩DP

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 21, M = (1 << N);
 4 int w[N][N]; //两点之间的距离
 5 int dp[M][N];
 6 int main() {
 7     int n;
 8     cin >> n;
 9     for (int i = 0; i < n; i++) {
10         for (int j = 0; j < n; j++) {
11             cin >> w[i][j];
12         }
13     }
14     memset(dp, 0x3f, sizeof dp); //求最小值要初始化为一个较大值
15     dp[1][0] = 0; //边界值
16     for (int i = 0; i < (1 << n); i++) { //所有状态
17         for (int j = 0; j < n; j++) { //所有点
18             if (i >> j & 1) {
19                 for (int k = 0; k < n; k++) { //枚举下从哪个点转移过来
20                     if (i >> k & 1) { //从k点转移过来
21                         dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
22                     }
23                 }
24             }
25         }
26     }
27     cout << dp[(1 << n) - 1][n - 1] << endl;
28     return 0;
29 }