进阶指南的第四题
主要考察状压dp
设状态dp[i][j] i表示当前走过的点的集合， j表示当前停在了哪个点？

这个状态该如何转移呢？
显然：可以用floyed得算法思路，不断枚举中间界限来尝试松弛操作。但需要注意的是：
** 集合i中必须要包含k 否则该状态就是不合法的(因为如果当前在的点是k点，那么我就肯定走过k点)**
按照刚才的思路，如果i中不包含j，那么该状态也是不合法的。
即：

if (i>>j&1)
    continue;

这里着重解释一下 if (i-(1<<j)>>k&1) 这句话的含义
1<<j写成二进制数就是10000000... （这里一共有j个零）
i-(1<<j) 就是把原本是i的第j位(因为dp[i][j]肯定是合法的，所以i的第j+1位一定是1。而且，集合i是从个位开始定义的，而j是从第0位开始枚举的)清零，即为把j标记为没有走过。

换言之，如果题中的编号是从1开始算的，那么if (i>>j&1) 就要写成 (i>>(j-1)&1) ,if (i-(1<<j)>>k&1)就要写成(i-(1<<(j-1))>>(k-1)&1)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAX=20;
int n;
int dp[1<<20][MAX];
int g[MAX][MAX];
int main(){
    cin>>n;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin>>g[i][j];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0;

    for (int i=1;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            if ((i>>j)&1)
                for (int k=0;k<n;k++)
                    if (i-(1<<j)>>k&1)
                        dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+g[k][j]);

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