最短Hamilton路径
Hamilton路径的介绍——百度百科

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出。

由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。（这里是区别于其他的概念的地方）

在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。——百度百科

题目：给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

思路：用二进制数字01表示当前点的状态（走过或者是没有走过）。

状态转移方程：$f[i|(1<<k)][k]=min(f[i|(1>>k)][k],f[i][j]+a[j][k])$

第一维使用一个数字的二进制表示已经到到达过了的点，第二维是当前你刚刚或者是即将到达的点。

来自于chdy的代码：

    memset(f,10,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<(1<<n);i++)//复杂度2^20*400==419430400
    {
        for(int j=0;j<n;j++)//枚举你在i的状态时刚刚到达的点
        {
            if((i&(1<<j))==0)continue;//说明j这个点不在i状态所选的范围内
            for(int k=0;k<n;++k)
            {
                if((i>>k)&1)continue;//k这个点已经被选过了 
                f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+a[j][k]);//i|(1>>k)的意思是将i在二进制表示下的第k位赋值为1 
            }
        }
    }
    put(f[(1<<n)-1][n-1]);//确保了起点是0，终点是n-1 

来自于蓝胖子的代码：

inline int hamilton(int n)
{
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;//第一个点是不需要花费的，因为到达第一个点不需要边上的花费 
    for(int i=1;i<(1<<n);i++)//i的二进制数表示的是n-1个点到达或者是不到达的方案，所有i的二进制的位数一定有n-1位 
        for(int j=0;j<n;++j)//枚举的是在i这种状态下的最后一个到达的点。
            if((i>>j)&1)//判断在i的状态下点j是否被用到，如果点j被用到的话，就可以进行下面的更新操作【松弛操作】 
                for(int k=0;k<n;++k)//用点k来更新[松弛]点j 
                    if((i^(1<<j))>>k&1)//如果说是点k不同于点j，而且点k在i这种状态下被经过，就说明点k可以来更新点j 
                        f[i][j]=min(f[i][j],f[i^(1<<j)][k]+a[k][j]);
    return f[(1<<n)-1][n-1];
}

$Nice$……