最短Hamilton路径（模板提）

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 int f[1 << 20][20], weight[20][20], n;//f[i][j]表示的时状态为i的集合,j 表示在这个状态下的位于的位置，f[i][j]表示的最小的值
  7 int hamilton(){
  8     memset(f, 0x3f, sizeof f);
  9     f[1][0] = 0;
 10     for(int i = 1; i < 1 << n; ++ i)//枚举状态，也就是几个点的集合，
 11         for(int j = 0; j < n; ++ j) if(i >> j & 1)//如果这个点是1那么，状态是成立的
 12         for(int k = 0; k < n; ++ k) if(i >> k & 1)
 13         f[i][j] = min(f[i][j], f[i^1<<j][k] + weight[k][j]); // i^1<<j上一个状态转移过来的结果
 14     return f[(1<<n)-1][n-1];
 15 }
 16 int main(){
 17 
 18     cin >> n;
 19     for(int i = 0; i < n; ++ i)
 20         for(int j = 0,a; j < n; ++ j)
 21             cin >> weight[i][j];
 22     cout << hamilton() << endl;
 23     return 0;
 24 }