POJ3311 Hie with the Pie（状压DP，Tsp）

忿忿的泥巴坨金牌会员 | 2022-8-10 06:03:37 | 显示全部楼层 | 阅读模式

楼主

主题 846|帖子 846|积分 2538

本题是经典的Tsp问题的变形，Tsp问题就是要求从起点出发经过每个节点一次再回到起点的距离最小值，本题的区别就是可以经过一个节点不止一次，那么先预处理出任意两点之间的最短距离就行了，因为再多走只会浪费更多的距离。
dp[S]表示当前已访问的节点集合为S,从u出发走完剩余节点回到起点的最短距离。

边界条件：dp[(1

使用道具举报