题解 P1171 【售货员的难题】

· · 题解

楼下说的对

可以用dp解

状压dp

但只有80，有两个点TLE，我目前不会优化了，希望有dalao指点

s利用二进制表示哪几个乡村已经访问过

或者可以理解为访问过的乡村的集合

dp[i][s]表示当走到 第i个乡村时

访问过的村庄集合为s时的最短路径

dp[i][s]=min(dp[i][s],dp[j][s ^ ( 1<< (j-1) )]+mp[j][i]) ; 1<= j <=n

s ^ ( 1<< (j-1) ) 表示的是集合 s 去掉元素 j 而得到的新的集合

这个在二进制的 0 1序中，手推一下就明白了

目标是 min（ dp[i][all]+mp[i][1] ）；1<=i<=n

大体的状压dp思路就这样

一些细节在代码有注释

#include<bits/stdc++.h>
using namespace std;
int n,mp[21][21],all,dp[21][1048580],ans=99999;
int read(){
    int ret=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())ret=ret*10+ch-'0';
    return ret;
}
int main(){
    n=read();
    all=(1<<n)-1;//all是全集 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j]=read();
    memset(dp,127/3,sizeof(dp)); 
    dp[0][0]=0; 
    //预处理由乡村1直接到达的 
    for(int i=1;i<=n;i++)dp[i][1<<(i-1)]=mp[1][i];
    for(int s=0;s<=all;s++){
        for(int i=1;i<=n;i++)
        if(s&(1<<(i-1)))
        //s一定要包含当前点的 
            for(int j=1;j<=n;j++)
                dp[i][s]=min(dp[i][s],dp[j][s^(1<<(i-1))]+mp[j][i]);
    }
    for(int i=1;i<=n;i++)
        ans=min(ans,dp[i][all]+mp[i][1]);
    cout<<ans;
}