State compression DP acwing 91 Shortest Hamilton path

State compression DP AcWing 91. The shortest Hamilton route

Original link

AcWing 91. The shortest Hamilton route

Algorithm tags

Binary status Compress DP

Ideas

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 20, M = 1 << N;
int a[N][N], f[M][N];
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;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read();
    rep(i, 0, n){
        rep(j, 0, n){
            a[i][j]=read();
        }
    }
    memset(f, 0x3f, sizeof f);
    //  No journey has been made at the initial point ,  Therefore, the initial value bit 0 
    f[1][0]=0;
    // i It means all the situations 
    rep(i, 0, 1<<n){
        rep(j, 0, n){
        	// j Indicates which point to go 
            if(i>>j&1){// j Not past 
            	// k Said go j Before this point , With k The shortest distance to the end 
                rep(k, 0, n){
                    if(i>>k&1){ //k Not past 
                        f[i][j]=min(f[i][j], f[i-(1<<j)][k]+a[k][j]);
                    }
                }
            }
        }
    }
    printf("%lld", f[(1<<n)-1][n-1]);
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support