Hamilton路径（模板题）

运用二进制状态压缩，模板题

• #include <iostream>
  #include <algorithm>
  #include <cstring>
  using namespace std;
  
  int f[1 << 20][20], weight[20][20], n;//f[i][j]表示的时状态为i的集合,j 表示在这个状态下的位于的位置，f[i][j]表示的最小的值
  int hamilton(){
      memset(f, 0x3f, sizeof f);
      f[1][0] = 0;
      for(int i = 1; i < 1 << n; ++ i)//枚举状态，也就是几个点的集合，
          for(int j = 0; j < n; ++ j) if(i >> j & 1)//如果这个点是1那么，状态是成立的
          for(int k = 0; k < n; ++ k) if(i >> k & 1)
          f[i][j] = min(f[i][j], f[i^1<<j][k] + weight[k][j]); // i^1<<j上一个状态转移过来的结果
      return f[(1<<n)-1][n-1];
  }
  int main(){
  
  
      for(int i = 0; i < n; ++ i)
          for(int j = 0,a; j < n; ++ j)
              cin >> weight[i][j];
      cout << hamilton() << endl;
      return 0;
  }