状态压缩dp

状态压缩，用二进制数来表示状态，从而达到状态转移的目的。
例题,最短哈密尔顿路径。
https://www.acwing.com/problem/content/93/
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =20;
const int M = 1<<20;
const int inf  = INT_MAX/2;
int n;
int dp[M][N];//状态为i，结尾为点j
int gra[N][N];
int main(void)
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&gra[i][j]);
        }
    }
    memset(dp,0x3f,sizeof dp);
    dp[1][0]=0;//起点为1，没走过任何路程
    for(int i=0;i<1<<n;i++)//枚举所有状态
    {
        for(int j=0;j<n;j++)//枚举所有结尾的点。
        {
            if((i>>j) &1)//状态i里面有j点，可以进行转移。
            {
                for(int k=0;k<n;k++)//枚举转移点k
                {
                    if(((i-(1<<j))>>k) & 1 )//状态i必须包含转移点k
                    {
                        dp[i][j] = min(dp[i][j],dp[i-(1<<j)][k]+gra[k][j]);
                        //cout<<dp[i][j]<<" ";
                    }
                }
            }
        }
    }
    printf("%d",dp[(1<<n)-1][n-1]);
}