分析
我们可以用状态压缩列出所有的方案路径比如说
1->2->4.
用二进制表示就是1101。题目要我们求到达第n个点的距离最小,我们的状态可以解释为f[i][j]为以i方案到达j点的最小的距离。但是我们的i方案不一定会到达j点所以要加以判断根据我们i的定义只需要确定j是第几个1就可以了所以当1&(i>>j)为1的时候就说明我们的方案一定会到达j。
下面我们来确定状态转移方程,我们选取一个终点k,i到达k之后再从k直接到达j,这些最小的点就是我们当前到j的最短的路径
状态转移方程
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j];
weight是两点之间的距离
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/17/%E6%9C%80%E7%9F%ADHamilton%E8%B7%AF%E5%BE%84/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!