91. 最短Hamilton路径
该题为状压dp，先说状态转移方程再解释 dp[x][y]表示到达y这个点后状态为x的最小路程。 那么设i为起点，j为起点i的状态,k为终点； 那么转移方程为dp[j|(1<<k)][k]=min(dp[j|(1<<k)][k],dp[j][i]+a[i][k]); j|(1<<k)的意思是在起点的状态下转移到终点的状态那么此时到达的对应位置为k，所以是dp[k][j|(1<<k)]，所以这里要判一下j时k这个位置是否走过，dp[i][j]+a[i][k]，表示转移到k时的路程。
#include<iostream> #include<stdio.h> #include<math.h> #include<string.h> #include<string> #include<vector> #include<queue> #include<algorithm> #include<deque> #include<map> #include<stdlib.h> #include<set> #include<iomanip> #include<stack> #define ll long long #define ms(a,b) memset(a,b,sizeof(a)) #define lowbit(x) x & -x #define fi first #define ull unsigned long long #define se second #define lson (rt<<1) #define rson (rt<<1|1) #define endl "\n" #define bug cout<<"----acac----"<<endl #define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0) using namespace std; const int maxn = 3e5 + 10; const int maxm = 1e4 + 50; const double eps = 1e-7; const int inf = 0x3f3f3f3f; const ll lnf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; int n; int a[33][33]; int dp[(1<<21)+10][21]; int main() { scanf("%d",&n); for(int i = 0;i < n; i++) { for(int j = 0;j < n; j++) { scanf("%d",&a[i][j]); } } ms(dp,inf); dp[1][0]=0; //dp[1][1]=0; for(int j=0;j<(1<<n);j++) { for(int i=0;i<n;i++) { if((1<<i)&j)//判断j的第i个位置是否已经走到，也就时可不可以当起点 { //cout<<j<<endl; for(int k=0; k < n; k++) { if(i==k)continue; if(!((1<<k)&j))//可不可以当终点 { dp[j|(1<<k)][k]=min(dp[j|(1<<k)][k],dp[j][i]+a[i][k]); } } } } } printf("%d\n",dp[(1<<n)-1][n-1]); return 0; }