刷题：最短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[x,z]。// 输出格式// 输出一个整数，表示最短Hamilton路径的长度。// 数据范围// 1 ≤ n ≤ 20// 0 ≤ a[i,j] ≤ 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[j];        memset(f, 0x3f, sizeof f);    f[1][0] = 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[j] = min(f[j], f[i - (1