AcWing 91. 最短Hamilton路径

状压DP，对于这种范围给到20的，1<<20并不大，dp[i][j]中i代表状态，表当前二十个二进制位中，有多少点已经走过，j代表的是当前状态中最后的点什么，我们维护这个二维数组，就能得到答案dp[(1<

#include 
#define LL long long
using namespace std;
int n;
int maps[30][30];
const int maxx = (1<<20)+2;
int d[maxx][20];
const int INF = 0x3f3f3f3f;
int main(){
   while(~scanf("%d",&n)){
       for (int i=0;i){
          for (int j=0;j){
              scanf("%d",&maps[i][j]);
          }
      }
       memset(d,0x3f,sizeof(d));
       d[1][0]=0;
       for(int i=1;i<(1<){
           for (int j=0;j){
               if((i>>j)&1){
                   //代表走过的点中有第j号点，i的第j位置的二进制位不为0
                    for (int k=0;k){
                        if((i^(1<>k & 1){
                            d[i][j]=min(d[i][j],d[i^(1<maps[j][k]);
                        }
                    }
                }
            }
       }
       printf("%d\n",d[(1<1][n-1]);
   }
    return 0;
}