17 位运算与状态压缩

#include <iostream>
using namespace std;
int main() {
    int a = 6, b = 3;                 // 6=110(2), 3=011(2)
    cout << (a & b) << endl;    // 2  按位与：110 & 011 = 010
    cout << (a | b) << endl;    // 7  按位或：110 | 011 = 111
    cout << (a ^ b) << endl;    // 5  按位异或：110 ^ 011 = 101
    cout << (1 << 5) << endl;   // 32，左移一位等于乘 2（1<<5 = 2^5）
    cout << (32 >> 2) << endl;  // 8，右移一位等于整除 2（32>>2 = 8）
    return 0;
}

// 集合表示：用整型的第 i 位表示"元素 i 是否在集合里"
int mask = 0;                     // 空集
mask |= (1 << 2);        // 加入元素 2（把第 2 位置 1）
mask |= (1 << 3);        // 加入元素 3（把第 3 位置 1）
// 判断元素是否在集合：右移后与 1 相与
cout << ((mask >> 2) & 1) << endl;   // 1（元素 2 在集合）
cout << ((mask >> 5) & 1) << endl;   // 0（元素 5 不在）

// 枚举集合 s 的所有非空子集（经典技巧，必背）
void enumSubset(int s) {
    for (int sub = s; sub; sub = (sub - 1) & s) {
        // 处理子集 sub
        // (sub-1)&s：去掉最低位 1 后仍限制在 s 内，依次得到全部子集
    }
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
const int INF = 1e9;
int dist[N][N];
int dp[1 << N][N];       // dp[mask][i]：已访问集合 mask，当前在 i 的最小距离
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> dist[i][j];

    for (int mask = 0; mask < (1 << n); mask++)   // 初始化全无穷
        for (int i = 0; i < n; i++) dp[mask][i] = INF;
    dp[1][0] = 0;                        // 从节点 0 出发，集合中只有 0

    for (int mask = 1; mask < (1 << n); mask++) {   // 枚举已访问集合
        for (int i = 0; i < n; i++) {               // 当前所在点
            if (!((mask >> i) & 1)) continue;      // i 不在集合里则跳过
            for (int j = 0; j < n; j++) {           // 下一步去 j
                if ((mask >> j) & 1 || i == j) continue;  // j 已在集合或原地
                int nxt = mask | (1 << j);          // 新集合 = 旧集合 ∪ {j}
                dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + dist[i][j]);
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1] << endl;   // 访问完全部点，最后停在 n-1
    return 0;
}