传送门
每个点最多走一次 因此我们用0,1表示一个点去没去过，这样的话，假如有5个点，10100就可以表示去过第一个点，去过第三个点，其他没有去过。
因此状态转移：dp[state][i]=min(dp[state][i],dp[state'][j]+dis[i][j])
最短路用floyd搞搞即可，state'里面的第i个城市的状态一定要和第j个一样。
ans=min(dp[max_state-1][i]+dis[0][i])
P.S. 代码来自这位大佬，因此本蒟蒻实在改不出来了（ 状压的题怎么这么多细节 草 ）
#include <cstdio> #include <algorithm> using namespace std; int const INF = 0xfffffff; int dp[(1 << 11)][11], n; int dis[11][11]; void Floyd() { for(int k = 0; k <= n; k++) for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) if(dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; } int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) scanf("%d", &dis[i][j]); Floyd(); for(int i = 0; i <= (1 << n) - 1; i++) { for(int j = 1; j <= n; j++) { if(i == (1 << (j - 1))) dp[i][j] = dis[0][j]; else { dp[i][j] = INF; for(int k = 1; k <= n; k++) if((k != j) && (i & (1 << (k - 1)))) //当前状态下 dp[i][j] = min(dp[i][j], dp[i ^ (1 << (j - 1))][k] + dis[k][j]); } } } int ans = dp[(1 << n) - 1][1] + dis[1][0]; for(int i = 2; i <= n; i++) ans = min(ans, dp[(1 << n) - 1][i] + dis[i][0]); printf("%d\n", ans); } }转载于:https://www.cnblogs.com/Patrickpwq/articles/9417615.html
