题目：最短Hamilton路径

题目描述

给定一张 $n$个点的带权无向图，点从 $0$ ~ $n$-1 标号，求起点 0 到终点 $n$-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数$n$。
接下来$n$行每行$n$个整数，其中第$i$第$j$个整数表示点$i$到$j$的距离（记为$a[i,j]$）。对于任意的$x,y,z$，数据保证 $a[x,x]$=0，$a[x,y]$=$a[y,x]$ 并且 $a[x,y]$+$a[y,z]$>=$a[x,z]$。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
$1≤n≤20$
$0≤a[i,j]≤
10^{7}$

输入样例：

输出样例：

题解

这应该也是一道很典型的状态压缩dp问题。~~为啥最近总是压缩DP?因为最近再学压缩dp,并且还学不明白:sob:~~

朴素算法

如果暴力枚举的话,那应该枚举 $n!$ 种情况,数据范围是$0$~$20$, 数据开到最大,就要枚举$20!$ 种情况, 显然不行。时间复杂度应该是$O(n!*n)$。

动态规划

状态表示$f[ i ][ j ]$

$ f[i][j] $所有从 $0$ 走到 $j$，走过的所有点是 $i$ 的所有路径。

例如 $i=(111011)_2$ 表示, 第1,2,4,5,6个点走过了。
边界条件
因为起点从0号点开始 $f[1][0] = 0$ ，最终需要的结果是 $f[(1<<n)-1][n-1]$ 。 $1<<n-1$ 就是$(111…1)_2$ 一共$n$个1，代表走过所有点了，$n-1$代表最后一步走到终点了。
状态计算
首先我们已经知道最后一个点是 $j$ 这个点了,我们就不考虑这个点，我们考虑是倒数第二个点k，枚举是哪一个点转移到 $j$ 就行了。

$f[i - {j} ][k]$ + $a[k][j]$ ,$i$中去掉第 $j$个点的情况，在加上由第$K$个点走向 $j$ 的距离,求最小值就可以转移到 $f[i][j]$。

代码

#include<iostream>
#include<cstring>

using namespace std;

const int M = 1<<20;
const int N= 20;
int n , f[M][N];
int a[N][N]; //带权无向图， 邻接矩阵。
int main(){
    cin>>n;
    for( int i = 0 ; i < n ; i++  )
        for( int j = 0 ;j < n ; j ++ )
            cin>>a[i][j];   

    memset( f, 0x3f , sizeof f) ;
    f[1][0] = 0;
    for( int i =0 ; i<1<< n ;i ++ )
        for( int j =0 ; j < n ;j ++ )
               if( i >>j & 1) //走到第j个点 
                   for( int k = 0; k < n ;  k ++ ) //假设是由第k个状态转移过来的
                        if((i - (1<<j)) >> k & 1)  //j 和k不能相同
                            f[i][j] = min( f[i][j] , f[i - (1 <<j)][k] + a[k][j]);

    cout<<f[(1<<n)-1][n-1];
    return 0;
}