【题目】

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

【题解】

状压dp裸题，即用状压思想压缩所有的可能的状态，把其变为二进制。而二进制上的第位，则代表第个点，而位置上为的可以理解为，这个点已经被走过了，为的话，可以理解为这个点还没有被走过。所以,状压后的可能性就是被表示为。而我们在这里可以用类似于弗洛尔伊德的做法（不知道也没事），即利用的复杂来进行路径长度的松弛。即循环可能性中，枚举已经走过的点，即代码中的，来寻找是否还有其它的路径，能使其当前状态的路径总长度缩减，而这就是松弛的操作，即两点的距离，依靠第三个点构成的路径，来缩短两点的距离。而代码中则是让当前状态变回还没有走过当前点的状态，然后判断这个被变化的状态加上的值能否使得路径总长度比之前的要小。到了最后的最后，即使最终的答案。

时间复杂度：

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)  
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); } 
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=20+5;
int masz[N][N];
int dp[(1<<20)+5][N];
int main(){
    int n; Sca(n); 
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            Sca(masz[i][j]);
    memset(dp,INF,sizeof(dp));
    dp[1][0]=0;
    for(int i=1;i<=(1<<n)-1;i++){
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                for(int k=0;k<n;k++){
                    dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+masz[k][j]);
                }
            }
        }
    }
    Pri(dp[(1<<n)-1][n-1]);    
}