Hamilton路径的定义：从0（起点）到n-1（终点）不重不漏地经过每个点恰好一次。
由于数据范围非常小，考虑状压。如NOIP2017宝藏一题，把状态压缩设为n个点是否已到达的二进制数。1表示到达过，0表示没到达过。
设计状态$f[i][j]$表示当前状态为i，目前处于点j的最短路径。在每一个状态下，我们枚举当前在哪里，并枚举当前在的这个地方是由哪个状态转移过来的。（即枚举的这两个地方其实都已经经过了。）那么之前的状态可以表示成$i xor (1<<j)$。
则有转移$dp[i][j]=min(dp[i][j],dp[(1<<j)xor i][k]+w[k][j])$;
Code
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 int n; 8 int w[50][50],dp[1500000][30]; 9 10 int main() 11 { 12 scanf("%d",&n); 13 memset(w,0x3f,sizeof(w)); 14 for(int i=0;i<n;i++) 15 for(int j=0;j<n;j++) 16 { 17 int z=0; 18 scanf("%d",&z); 19 w[i][j]=w[j][i]=min(w[i][j],z); 20 } 21 memset(dp,0x3f,sizeof(dp)); 22 dp[1][0]=0; 23 for(int i=1;i<(1<<n);i++) 24 for(int j=0;j<n;j++) 25 { 26 if(!((i>>j)&1)) continue; 27 for(int k=0;k<n;k++) 28 { 29 if(!((i>>k)&1)) continue; 30 dp[i][j]=min(dp[i][j],dp[(1<<j)^i][k]+w[k][j]); 31 } 32 } 33 printf("%d ",dp[(1<<n)-1][n-1]); 34 return 0; 35 }
* 细节：用邻接矩阵存图的时候需要开始赋成很大。
节点标号是0~n-1，与二进制的习俗相似。所以不用注意很多