状压DP

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;
const int INF = 0x3f3f3f3f;

int g[N][N];    // g[i][j] = 城市 i 到城市 j 的距离
int dp[1<<N][N]; // dp[S][i] = 经过的城市集合为S，当前在城市i的最短距离
int n;           // 城市数量

int tsp() {
    // 第1步：初始化——把所有状态设为"不可达"
    memset(dp, 0x3f, sizeof(dp));
    // 0x3f 在 memset 中表示把每个字节设为 0x3f
    // 对于 int 数组，相当于每个元素设为 0x3f3f3f3f（一个很大的数）

    // 第2步：初始状态——从城市0出发，只经过了城市0
    // 1 = 1<<0 = 二进制 000...001，表示"只有第0位是1"
    dp[1][0] = 0;

    // 第3步：枚举所有城市集合 S
    for (int S = 1; S < (1 << n); S++) {
        // 枚举"当前在哪个城市 u"（u 必须在集合 S 中）
        for (int u = 0; u < n; u++) {
            // 如果 u 不在集合 S 中，跳过
            if (!(S & (1 << u))) continue;

            // 枚举"下一个去哪个城市 v"（v 必须不在集合 S 中）
            for (int v = 0; v < n; v++) {
                if (S & (1 << v)) continue;  // v 已在 S 中，跳过

                // 转移：从 u 去 v
                // 新集合 = S 加入 v = S | (1<<v)
                int newS = S | (1 << v);
                dp[newS][v] = min(dp[newS][v],
                    dp[S][u] + g[u][v]);
                // 含义：在状态 S 下从 u 出发去 v，
                // 比已经记录的距离更短就更新
            }
        }
    }

    // 第4步：求答案——所有城市都经过，再回到城市0
    int ans = INF;
    int fullS = (1 << n) - 1;  // 全1，表示所有城市都经过了
    for (int u = 1; u < n; u++) {
        // 从每个城市 u 出发，回到城市 0
        ans = min(ans, dp[fullS][u] + g[u][0]);
    }
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    cout << tsp() << endl;
    return 0;
}