题解 P1171 【售货员的难题】

· · 题解

看不懂楼下p党的代码 只好自己写一份c++了

思想跟楼下差不多 貌似这题正解是状压dp 无奈我不会写

直接上代码 注释在代码里 10个点 851ms

#include<iostream>
#include<cstdio> 
#include<algorithm>
using namespace std;
int n,min1=200010,sum,minv[21],mind=200010;
bool vis[21];
struct node{
    int dis,id;
}a[21][21],b[21];
void dfs(int q,int last){
    if(q==n){
        min1=min(min1,sum+minv[last]);
        return ;
    }
    for(int i=2;i<=n;i++)
        if(!vis[a[last][i].id]){
            if(sum+a[last][i].dis>min1)return;//如果当前已走的距离已经大于当前最优值 返回 
            if(sum+a[last][i].dis+n-q+mind>=min1)return ;
            //假想最小值剩下的村庄（n-q）的距离都是1 并且最后回到1的时候的距离也是最小的。
            //如果此时还是超了当前最小值 后面的就都不需要搜了。 
            vis[a[last][i].id]=1;
            sum+=a[last][i].dis;
            dfs(q+1,a[last][i].id);
            vis[a[last][i].id]=0;
            sum-=a[last][i].dis;
        }
}
bool cmp(node a,node b){
    return a.dis<b.dis;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j].dis;
            a[i][j].id=j; 
        }
        minv[i]=a[i][1].dis;//minv[i]表示i村庄到1的距离 
        if(i!=1)mind=min(mind,minv[i]);//表示所有村庄到1的最短距离（不包括1到1） 
        sort(a[i]+1,a[i]+n+1,cmp);//读数据时每次得到一行的值后对边值排序。这样可以更快得到较优值。 
    }
    vis[1]=1;
    dfs(1,1);
    cout<<min1;
    return 0;
}