最短Hamilton路径

CH

(n-1)不重不漏地经过每个点恰好一次.

(f[i][j])表示当前状态对应的二进制数为i,且位于点j的最短路径.

(f[i][j]=min(f[i][j],f[i xor (1<<j)][k]+w[k][j]))

(i xor(1<<j))是上一次的状态,这保证了上一次状态的第k位为1)

(n-1)号点.

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
const int N=20;
int w[N][N],f[1<<N][N];
int main(){
    int n=read();
    for(int i=0;i<n;i++)//这里记得配合二进制数从0开始存
		for(int j=0;j<n;j++)
	    	w[i][j]=read();
    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)
				for(int k=0;k<n;k++)
		    		if(((i^(1<<j))>>k)&1)
						f[i][j]=min(f[i][j],f[i^(1<<j)][k]+w[k][j]);
    printf("%d
",f[(1<<n)-1][n-1]);
    return 0;
}