最短Hamilton路径

题目描述

给定一张 $n$ 个点的带权无向图，点从 $0∼n−1$ 标号，求起点 $0$ 到终点 $n−1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。

输入样例：

xxxxxxxxxx
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

其中$5$代表一共有$5$个点，下面$5\times5$的矩阵中$A[i][j]$代表点$i$到点$j$的路径。

输出样例：

xxxxxxxxxx
18

输出就直接输出答案即可。

解题思路

• 首先用一个数$state$来表示当前状态，数字$state$二进制下的第$i$位表示点$i$是否经过过(1表示已经经过过了)。

• 然后用一个数组$f[state][j]$表示终点位于点$j$且路径状态位$state$的最短总路径。

  其中合法的$f[state][j]$必须满足$state$的第$j$位是$1$(因为终点在$j$表面$j$点经过过)，即$state>>j\&1$为真。

• $f[state][j]$的值为所有能一步到达$j$的点$k$中，$f[state\_k][k]+k到j的路径$的最小值。

• 初始值：起点是$0$，这时候只经过了点$0$，所以$state$只有最低为是$1$其他位都是$0$，$state$初始值就是$1$。又因为$0$到$0$的距离是$0$，所以初始值$f[1][0]=0$。

需要注意-的优先级大于>>

对核心代码的讲解：

这里可以先参考一下后面的完整代码

• memset(f, 0x3f, sizeof(f)) 赋初值为“无穷大”

• xxxxxxxxxx
  for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
          cin>>A[i][j];
  

  输入每两点之间的距离

• f[1][0]=0初始化起点自身的状态

• xxxxxxxxxx
  for(int i=0;i<1<<n;i++) // 先枚举每种状态i
      for(int j=0;j<n;j++) // 再枚举这种状态下的终点j
          if(i>>j&1) // 这种状态的第j位必须是1才有意义
              for(int k=0;k<n;k++) // 最后枚举这种到点j的上一个点k
                  if((i-(1<<j))>>k&1) // (i-(1<<j))是上一种状态，它的第k位必须是1
                      f[i][j]=min(f[i][j], f[i-(1<<j)][k]+A[k][j]); // 取所有能到达这一点的选项中的最小值
  

• cout<<f[(1<<n)-1][n-1]<<endl 输出最终结果：状态是起点到终点的每个点都经过，终点是n-1。