售货员的挑战：状态压缩动态规划解法

问题背景与目标：

售货员难题要求找到一条路径，使得售货员从起点出发，访问所有指定的城市后返回起点，且总旅行距离最短。这个问题可以通过状态压缩动态规划（状压DP）来高效求解。

在该方法中，我们定义dp[S][i]表示当前访问过的城市集合为S，并且最后访问的城市为i时的最小成本。其中，S是一个二进制数，每一位代表一个城市的访问状态（0未访问，1已访问）。状态转移方程为：dp[S | (1 <<(j - 1))][j] = min(dp[S | (1 <<(j - 1))][j], dp[S][k] + e[k][j])，其中e[k][j]表示从城市k到城市j的距离。

最终结果是在所有可能的状态中，选择包含所有城市且最后回到起点1的最小成本路径，即计算dp[(1 <

为了确保算法能够正确追踪从任意城市回到起点1的路径，我们在状态转移过程中需要额外记录每个状态下的最后一个到达的城市信息。

以下是C++语言实现的代码示例：

#include
#include
#include
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
const int N = 21, INF = 0x3f3f3f3f;
int e[N][N], dp[1 <<(N - 1)][N], A[N], B[N];
int main() {
    int n, t;
    scanf("%d", &n);
    t = (1 <    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &e[i][j]);
    m(dp, INF);
    dp[1][1] = 0;
    for (int i = 1; i         int oA = 0, oB = 0;
        for (int j = 1; j <= n; ++j)
            (i & (1 <<(j - 1))) ? A[++oA] = j : B[++oB] = j;
        for (int jj = 1; jj <= oB; ++jj)
            for (int kk = 1; kk <= oA; ++kk) {
                int j = B[jj], k = A[kk], d = i | (1 <<(j - 1));
                dp[d][j] = min(dp[d][j], dp[i][k] + e[k][j]);
            }
    }
    int ans = INF;
    for (int i = 2; i <= n; ++i)
        ans = min(ans, dp[t - 1][i] + e[i][1]);
    printf("%d\n", ans);
}