洛谷P1171 售货员的难题 题解

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

题意：TSP问题。

某乡有\(n\)个村庄(\(1<n \le 20\))，有一个售货员，他要到各个村庄去售货，各村庄之间的路程\(s(0<s<1000)\)是已知的，且\(A\)村到\(B\)村与\(B\)村到\(A\)村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为\(1\)，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

题目应该保证了有解。

经典的状压dp

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

则有

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

代码：

#include <bits/stdc++.h>
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<a)a=b;}
signed main()
{
    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<<n; i++)
    for(int j=1; j<=n; j++) 
    if( (i>>(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<<n)-1][i]+g[i][1]);
    cout << mn << endl;
    return 0;
}