bc #52 div 2 B || hdoj 5418 Victor and World(tsp问题,状压dp)

比赛的时候一看,tsp么

前些天好像刚写过一个clean robot什么的

然后发现n才16,而m很大..

应该有很多重复的.

那么我们取油费最少的.

然后先做一遍 floyd

之后我写了一个dfs…TLE 了…sad

正解是状压dp

虽然没写过状压dp

但是之前写过一道状态压缩的bfs

所以理解起来没有问题.

这道题的做法是: 

用dp[i][j]表示当前访问国家的状态为s,要访问的国家为j的时候的最小费用.i是二进制,i的第p位为1表示第p个国家已经访问过了,否则表示没有访问过.

那么状态转移方程则为:dp[i|(1<

初始化的时候d[i][i] =0,其他为inf

dp[0][0] 表示要访问第一个国家且没有访问国人国家的时候的状态,此时花费为0

然后先枚举访问国家的状态,再枚举访问的国家.