Abstract：#动态规划#状压DP#TSP问题
1. 题目
- 题目：Luogu P1171 售货员的难题
- 核心思路：状态压缩动态规划。定义
dp[status][cur]表示当前已经访问过的城市集合为status，且当前位于城市cur，要访问完所有剩余城市并最终返回城市0的最短路径长度。转移时，枚举下一个未访问的城市i，则dp[status][cur] = min(G[cur][i] + dp[status | (1<<i)][i])。 - 复杂度：时间复杂度O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)（每个状态枚举n个城市），空间复杂度O ( n × 2 n ) O(n\times 2^n)O(n×2n)。
2. 代码
#include<iostream>#include<vector>#include<climits>usingnamespacestd;constintMAXN=25;intn;vector<vector<int>>G(MAXN,vector<int>(MAXN,0));intf(intstatus,intcur,vector<vector<int>>&dp){if(dp[status][cur]!=-1)returndp[status][cur];if(status==((1<<n)-1))returnG[cur][0];intans=INT_MAX;for(inti=0;i<n;++i){if((status&(1<<i))==0){ans=min(ans,G[cur][i]+f(status|(1<<i),i,dp));}}dp[status][cur]=ans;returnans;}intmain(){cin>>n;for(inti=0;i<n;++i){for(intj=0;j<n;++j){cin>>G[i][j];}}vector<vector<int>>dp(1<<n,vector<int>(n,-1));cout<<f(1,0,dp);return0;}3. 心得
边界条件：做题时忽略了这一点。当所有城市都已访问（status == (1 << n) - 1）时，需要返回起点0，代价为G[cur][0]。
位运算优先级：在判断某位是否为0时，
status & (1 << i)必须加括号，因为==的优先级高于&。误写为if (status & (1 << i) == 0) 会被解析为status & ((1 << i) == 0)，永远为0，导致条件永远不成立。这是一点务必牢记。
4. 相关题目
- LeetCode 847. 访问所有节点的最短路径
