Solution to the shortest Hamilton path problem

Title Description

Given a sheet $n(n<=20)$ A weighted undirected graph of points , Point from $0n-1$ Mark well , Find the starting point $0$ To the end point $n-1$ The shortest of $hamilton$ route

$hamilton$ The definition of path is from $0$ To $n-1$ Pass through every point exactly once without weight or leakage .

Input

first line $n$

Next one $n\ast n$ The adjacency matrix of ,$a[i][j]$ From point to point i point-to-point j Distance between points of

Output

a line , The shortest $hamilton$ The length of the path

Examples

The sample input 1

2
0 1
1 0

Sample output 1

1

solution

First, violence , Think of every point $dfs$
however ！
The time complexity of the search is $O(n!)$, Consider optimizing
We notice every moment
If you know which points have been passed and the current point
You can make the next decision
And the decision has nothing to do with the order in which these points are passed
Make $F[i][S]$ The set of points that have been passed is $S$, At present The location is $i$ Minimum path length
How to represent a collection :
take $S$ As a $n$ Bit binary number , The first $i$ A point was passed , If and only if $S$ The binary number of $i$ Is it 1
Solving object ：$F[n][(1<<n)-1]$, It means that all points have been passed

AC code

int main(){
    
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<=n;j++){
    
			cin>>a[i][j];
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1][1]=0;// Select only 1 of course  by 0
	for(int j=1;j<(1<<n);j++){
    
		for(int i=2;i<=n;i++){
    
			if((1<<(i-1))&j)continue;// state j Already contains i
			for(int k=1;k<=n;k++){
    
				if(k==i)continue;//dp[i][j]: This election i, Status as j Length of hour  
				dp[i][j+(1<<(i-1))]=min(dp[i][j+(1<<(i-1))],dp[k][j]+a[k][i]);
			}
		}
	}
	cout<<dp[n][(1<<n)-1];// It's over 
	return 0;
}

End of the flower *
*,°:.*(￣▽￣)/$:.°* .