刷题：最短Hamilton路径
题目名称：AcWing - 91. 最短Hamilton路径时间：2025年6月19日
知识点：二进制, 状态压缩DP
网址：AcWing - 91. 最短Hamilton路径
来源：《算法竞赛进阶指南》打卡活动
个人感想：这是一道非常标准的状态压缩dp模板题，第一次遇到状态压缩dp
思路：
[*]这是一道从来没有学过的全新的题型，故我一开始完全没有任何思路，随后我看着y总的视频讲解和ai的帮助慢慢理解了什么是题目信息转化为状态压缩dp的问题。
[*]我认为 本题的关键是理解为什么时间复杂度是 2^n * n，
也就是为什么仅凭当前所有点是否走过的状态所组成的0/1集合所转换成的数字 和 当前所在的终点 就可以表示和筛选所有的路径组合。
收获：（有的话就写）
<ul>if(a & 1) : 等效于求a的二进制的最后1位是不是1；
a >> b（a =a。// 输出格式// 输出一个整数，表示最短Hamilton路径的长度。// 数据范围// 1 ≤ n ≤ 20// 0 ≤ a ≤ 10^7// 样例// 输入样例：// 5// 0 2 4 5 1// 2 0 6 5 3// 4 6 0 8 3// 5 5 8 0 5// 1 3 3 5 0// 输出样例：// 18// 题目解析:只需要考虑所有点的状态（用二进制表示）以及目前停留在了哪个点。#include#include#includeusing namespace std;#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const int N = 20, M = 1 > n; for(int i = 0; i < n; i++) for(int j = 0 ;j < n; j++) cin >> weight; memset(f, 0x3f, sizeof f); f = 0; // 初始状态，起点为0，状态为1（即第0个点被访问过），此时1的二进制为000...001 for(int i = 0; i < (1 > j) & 1) // 如果第j位是1，说明第j个点被访问过 for(int k = 0; k < n; k++) // 枚举所有的点（这里的点指的是未访问过的点） if((i >> k) & 1 && k != j) // 如果第k位是1，说明第k个点没有被访问过 f = min(f, f[i - (1 谢谢分享，辛苦了 前排留名，哈哈哈 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 收藏一下 不知道什么时候能用到 用心讨论，共获提升！ 感谢发布原创作品，程序园因你更精彩 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了 鼓励转贴优秀软件安全工具和文档！ 鼓励转贴优秀软件安全工具和文档！ 感谢，下载保存了 感谢分享，学习下。 过来提前占个楼 感谢分享，学习下。 感谢分享，学习下。 谢谢分享，试用一下 过来提前占个楼 东西不错很实用谢谢分享