洛谷P1171 售货员的难题 题解

题目链接：P1171 售货员的难题

题意：TSP问题。

某乡有 n n n个村庄( 1 < n ≤ 20 1

题目应该保证了有解。

经典的状压dp

设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示目前走过的结点的状态为 i i i ，现在在 j j j 结点

则有

dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+g[k][j])

代码：

#include 
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)((1<<20)+2)

int n,g[25][25],dp[N][22];
void Min(int &a,int b){if(b
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(dp,0x3f,sizeof(dp));
    cin >> n;dp[1][1]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin >> g[i][j];
    for(int i=1; i<1<>(j-1))&1 )
        for(int k=1; k<=n; k++)
        if( k!=j && ((i>>(k-1))&1) )
            Min(dp[i][j],dp[i^(1<<(j-1))][k]+g[k][j]);
    int mn=0x3f3f3f3f;
    for(int i=1; i<=n; i++)
        Min(mn,dp[(1< 
转载请说明出处