T20:售货员的难题

1）题目意思

有 n 个村庄（编号 1 到 n），村庄之间是有向路，从 i 到 j 的距离是 s[i][j]，一般 s[i][j] 不等于 s[j][i]。

售货员从村庄 1（商店在 1）出发，要把 每个村庄恰好去一次，最后再回到村庄 1。

问最短总路程是多少，输出这个最小值。

2 <= n <= 20。

这就是经典的 TSP（旅行商）有向版。

---

2）思路解析（状态压缩 DP）

因为 n<=20，可以用二进制 mask 表示已经访问过哪些村庄。

• mask 的第 i 位为 1 表示村庄 i 已访问（这里用 0..n-1 表示村庄 1..n）
• 必须从村庄 0（也就是 1 号村）出发

状态定义

dp[mask][i] 表示：

• 从村庄 0 出发
• 访问过的集合为 mask（一定包含村庄 0）
• 当前停在村庄 i

的最短路程。

初始化

• dp[1<<0][0] = 0，表示只在起点

转移

从 dp[mask][i] 走到一个没访问过的 j：

• dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + s[i][j])

答案

当所有村庄都访问完 FULL=(1<<n)-1，最后要回到 0：

• ans = min(dp[FULL][i] + s[i][0])

复杂度

• 状态数约 2^n * n
• 转移约 2^n * n^2

n=20 可以通过。

---

3）代码

#include <bits/stdc++.h>
using namespace std;

const long long INF=(1LL<<62);                         // 定义一个很大的数当作无穷大

static int s[20][20];                                  // s[i][j] 存从 i 到 j 的距离
static long long dp[1<<20][20];                        // dp[mask][i] 状压DP数组

int main(){                                            // 主函数入口
    ios::sync_with_stdio(false);                       // 加速输入输出
    cin.tie(nullptr);                                  // 加速输入输出

    int n;                                             // 村庄数量
    cin>>n;                                            // 读入 n

    for(int i=0;i<n;i++){                              // 读入距离矩阵
        for(int j=0;j<n;j++){                          // 读入距离矩阵
            cin>>s[i][j];                              // 读入 s[i][j]
        }
    }

    int FULL=(1<<n)-1;                                 // FULL 表示所有村庄都访问过

    for(int mask=0;mask<=FULL;mask++){                 // 初始化dp为INF
        for(int i=0;i<n;i++){                          // 初始化dp为INF
            dp[mask][i]=INF;                           // 设为不可达
        }
    }

    dp[1][0]=0;                                        // 起点为0(村庄1)，只访问它，距离为0

    for(int mask=1;mask<=FULL;mask++){                 // 枚举所有访问集合
        for(int i=0;i<n;i++){                          // 枚举当前所在村庄 i
            if(!(mask&(1<<i)))continue;                // 如果 i 不在集合里，则该状态无意义
            long long cur=dp[mask][i];                 // 取出当前最短距离
            if(cur>=INF)continue;                      // 不可达则跳过

            for(int j=0;j<n;j++){                      // 枚举下一步要去的村庄 j
                if(mask&(1<<j))continue;               // 如果 j 已访问过则不能再去（要求恰好一次）
                int nmask=mask|(1<<j);                 // 新集合把 j 加进去
                dp[nmask][j]=min(dp[nmask][j],cur+s[i][j]); // 更新最短距离
            }
        }
    }

    long long ans=INF;                                 // 答案初始化为INF
    for(int i=0;i<n;i++){                              // 枚举最后停在的村庄 i
        ans=min(ans,dp[FULL][i]+s[i][0]);              // 从 i 回到起点0，取最小
    }

    cout<<ans<<endl;                                   // 输出答案
    return 0;                                          // 程序结束
}