最短Hamilton路径

CH

题意:给定一张(n(n≤20))个点的带权无向图，点从 (0~n-1)标号，求起点(0)到终点(n-1)的最短(Hamilton)路径.(Hamilton)路径的定义是从(0)到(n-1)不重不漏地经过每个点恰好一次.

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

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

其中((i>>j))&(1=1)(保证i的第j位为1),((ixor(1<<j)>>k))&(1=1)((i xor(1<<j))是上一次的状态,这保证了上一次状态的第k位为1)

初始化(f[1][0]=0)表示刚开始状态为1,即只经过了点0,且位于点0时的最短路径为0.其余赋为无穷大.目标(f[(1<<n)-1][n-1]),n为二进制数,每一位都为1的值为((1<<n)-1),根据(Hamilton)路径的定义,最后肯定是位于(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;
}