hie专题

POJ 3311 Hie with the Pie(TSP问题DP解)

题目:Hie with the Pie 题意:从0出发,走n个城市,最后回到0点,求最少花费 分析:状态压缩:dp[i][j]表示在i状态下,当前遍历第j个点的最小值            初始化:dp[1<<i][i] = d[0][i]             状态转移:dp[i][j] = min(dp[s][k] + d[k][j]) 其中s是i的子状态,在状态i的基础上,第j位为