注意,循环顺序不能更换:
正确的更新顺序:先确定小的二进制状态i,再去更新大的状态i(因为更新大i时会用到小i的值)
如果先更新最后一个点j,找了倒数第二个点k,但是h[i-(1<<j)][k]
未必是已确定的最小值,这就会犯错。
所以第一重循环必须是二进制状态,第二重循环才是最后一个点。
#include <bits/stdc++.h>
using namespace std;
const int N = 21;
int n;
int d[N][N];
int h[1<<N][N];
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++){
for (int j = 0; j < n; j ++ ){
scanf("%d", &d[i][j]);
}
}
memset(h, 0x3f, sizeof h);
h[1][0]=0;
for (int i = 0; i < 1<<n ; i ++ ){
for (int j = 0; j < n; j ++ ){
if(i>>j&1){
for(int k=0;k<n;k++){
if((i-(1<<j))>>k&1){
h[i][j]=min(h[i][j],h[i-(1<<j)][k]+d[k][j]);
}
}
}
}
}
printf("%d",h[(1<<n) -1][n-1]);
return 0;
}