Shortest Hamilton path (pressure DP)

subject

Given a sheet $n$ A weighted undirected graph of points , Point from $0\sim n-1$ label , 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 repetition or leakage .

Input format
Enter the integer in the first line $n$.

Next n Every line $n$ It's an integer , Among them the first $i$ Xing di $j$ An integer represents a point $i$ To $j$ Distance of （ Write it down as $a[i,j]$）.

For arbitrary $x,y,z$, Data assurance $a[x,x]=0$,$a[x,y]=a[y,x]$ also $a[x,y]+a[y,z]\ge a[x,z]$.

Output format
Output an integer , Means shortest Hamilton The length of the path .

Data range
$1\le n\le 20$
$0\le a[i,j]\le 10^7$
sample input ：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5

1 3 3 5 0
sample output ：

18

Pressure DP

$f[i][j]:f[i][j]surfaceinfrom0goToj,gotooOftheYesspotyesiOftheYesroadpath$

1. According to the meaning of the above state , We'll think about it very well

2. Since each f[i][j] It means from 0 Go to the j, All the points reached are i The path of , How to divide sets ?

3. Find the last difference of each scheme according to , We can find that each point can come from other points

4. If we start from a certain point k Come to the point j, Then our current state does not include j Of , Because I haven't reached j

5. according to 4 We can draw f[i][j] Can be f[i-(j)][k]+g[j][k]. explain (j):j Binary representation of this point ,g[j][k]:j Go to the k Distance of

6. Define according to the state : initialization f For negative infinity ——————————f[1][0]=0:(0 The distance to oneself must be 0)

7. The final answer is to go to n-1 Number point , And all points have passed ：f[(1<<n)-1][n-1]

---

AC Code （C++）

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=20,M=1<<N;

int f[M][N];   //f[i][j] From 0 Go to the j, All the points passed are i All the paths   example :i=110011(0 It means you haven't walked ,1 Representative walk , And on the far right is 0 This point )
int n;
int w[N][N];  //w[i][j] Express i To j The distance from this point 

int main(){
    
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    
        for(int j=0;j<n;j++){
    
            scanf("%d",&w[i][j]);
        }
    }

    memset(f,0x3f,sizeof f);   // Because the shortest path is required , Initialize to positive infinity 
    f[1][0]=0;  // The first point is that there is no cost 

    for(int i=0;i<1<<n;i++){
      // Enumerate all States of points 
        for(int j=0;j<n;j++){
       // Number of enumeration points 
            if(i>>j&1){
      //i>>j: seek i Of the j Digit number .  If &1 establish , Then represent j This point has passed 
                for(int k=0;k<n;k++){
      //k->j
                    if(i>>k&1 && j!=k){
       // Just like the above judgment ,  Express k This point goes by and is not yourself 
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);  // Judge whether this scheme is the best or from i->k, Again from k->j The optimal 
                    }
                }
            }
        }
    }
    printf("%d",f[(1<<n)-1][n-1]);  // Optimal solution 
    return 0;
}