题目描述

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
翻译：自己到自己的花费为0，是个无向图，两点之间的路径已经最短值（可以理解成已经用多源最短路的算法处理过）

输入样例

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

算法1

(状压dp) $O(n^2*2^n)$

个人对于dp的理解：优雅的暴力，通过查询已经计算过的值来降低复杂度，但是也会丢失一定的数据

对于算法的理解还不够深刻，难免有所疏漏，如有还请大佬不吝赐教

另memset()
memset是按照字节填充,即8位一填充，所以所填充的数要属于[0-255],感谢群内大佬DragonHawk不吝赐教
按此逻辑填充每个字节均为0x3f=63=00111111,所以每个数都被填充成0x3f3f3f3f=1,061,109,567 
如果填充成255，那么数字就会变成-1,如果填充成127,那么inf+inf就会变成负数，因此填充63=0x3f

C++ 代码

/*
    Name:AcWing 91. 最短Hamilton路径
    Author:wyz
    Date:2019/4/1 8:17:35
    Note:状压dp 

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 20, M = 1 << 20;
int dp[M][N], map[N][N];//dp用来存最短路的值,map用来储存图 
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> map[i][j];
    memset(dp, 0x3f, sizeof dp); 
    //dp[i][j]表示已经遍历过集合i中的顶点，并且在第j个城市结束 
    dp[1][0] = 0;//初始化,从0点出发,集合1(只有第0点遍历过了，并且停在0，所以第0位为1其他位为0)，费用为0
    //开始动归
    for (int i = 0; i < (1 << n); i ++ )
        for (int j = 0; j < n; j ++ )
            if ( (i >> j) & 1) {//按照定义：dp[i][j]在j点结束，所以j点必然被访问过。 
                //遍历集合i中的所有遍历过的非j节点
                for (int k = 0; k < n; k ++ )
                    if (i - (1 << j) >> k & 1) {
                        //i - (1 << j)是除去j的集合i
                        //dp[i][j]的最短路径(再次重点：此时是以j为最终节点)应该是从其所有子集中，所有其他节点到达j点的最小值
                        //例如 i = 01011 j = 3 表示dp[i][j]已经遍历过了0、1、3号节点,并且以3为终点
                        //那么dp[11][3]=dp[3][0]和dp[3][1]和INF中的最小值
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + map[k][j]);
                    }
            }
    //输出已经遍历所有城市,并且终点在n-1的最短路 
    cout << dp[(1 << n) - 1][n - 1] << endl;
    return 0;
}