题目背景

数据有更改

题目描述

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

输入输出格式

输入格式：

村庄数n和各村之间的路程(均是整数)。

输出格式：

最短的路程。

输入输出样例

输入样例#1： 

30 2 11 0 22 1 0

输出样例#1： 

3

说明

输入解释

3 {村庄数}

0 2 1 {村庄1到各村的路程}

1 0 2 {村庄2到各村的路程}

2 1 0 {村庄3到各村的路程}

 

Solution:

法一：

　　经典的状压dp题目。设f[i][j]表示某个状态的最短距离，其中i的二进制表示下的各位若为1则表示该点被访问过，j表示当前在j点，则容易得到状态转移方程：

　　f[i][j]=min{f[iυ{v}][v]+w[j][v]} 

由于最后要回到起点1，所以最后判断一下:

　　ans=min{f[(1«n)-1][i]+w[i][1]}。

状压代码：

 

#include
        
         #define il inline#define ll long longusing namespace std;const int N=1<<20;int n,w[25][25],f[N][22],ans=0x3f3f3f3f;int main(){    ios::sync_with_stdio(0);    cin>>n;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)cin>>w[i][j];    memset(f,0x3f,sizeof(f));    f[1][1]=0;    cout<
         
          <
         
        

 

 

 

法二：

　　当然本题也可以搜索+剪枝。

　　剪枝1：优化搜索顺序，按边从小到大排序。

　　剪枝2：最优性剪枝，若大于当前最优值则return。

　　剪枝3：可行性剪枝，将当前到没访问的点的距离都假设为1，若当前走过的距离加上没访问的点个数仍大于当前最优值，则return。

搜索代码：

 

#include
        
         #include
         
           #include
          
           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
           
            >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<