《算法競賽進階指南》

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;
}