2596 售货员的难题

 

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 钻石 Diamond

 

 

 

题目描述 

Description

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

输入描述 

Input Description

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

输出描述 

Output Description

最短的路程

样例输入 

Sample Input

3

0 2 1

1 0 2

2 1 0

样例输出 

Sample Output

3

数据范围及提示 

Data Size & Hint

本题可用最短路思想、搜索来解决，但是可能无法通过一组极限数据（且效率较低）。建议按树状DP考虑！

分类标签 Tags 

 

   

 

AC代码1：

/*  不会什么树形DP，我做的是spfa（其实floyed就可以）+深搜+剪枝  首先将边反向，spfa处理所有点到1的距离，以备剪枝使用  然后深搜得到答案  剪枝：利用spfa得到的距离，当当前的dis+(n-t)*minn+f[x]>ans时，剪枝    （minn是矩阵中的最短距离，n-t是还有几步可以遍历完所有的村庄） */#include
          
           #include
           
            #include
            
             #include
             
              #define M 20#define INF 3000000using namespace std;int map[M][M],f[M],n,ans=INF,min1=INF;int a2[M][M];bool vis[M];queue
              
                q;int read(){    char c=getchar();int num=0,flag=1;    while(c<'0'||c>'9'){
        if(c=='-')flag=-1;c=getchar();}    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}    return num*flag;}void dfs(int x,int t,int dis){    if(dis>ans)return;    if(dis+(n-t)*min1+f[x]>ans)return;    if(t==n)    {        ans=min(ans,dis+map[x][1]);        return;    }    for(int i=1;i<=n;i++)      if(!vis[i])      {          vis[i]=true;          dfs(i,t+1,dis+map[x][i]);          vis[i]=false;      }}void spfa(){    q.push(1);    vis[1]=1;    f[1]=0;    while(!q.empty())    {        int x=q.front();        q.pop();        vis[x]=0;        for(int i=1;i<=n;i++)          if(a2[x][i]&&f[x]+a2[x][i]
              
             
            
           
          

AC代码2：

#include
          
               #include
           
            using namespace std;#define N 51 int n,tr[N][N],m=0x7fffffff;bool vis[N];void run(int p,int d,int s){        int r;        if(d==n){        if(s+tr[p][1]
            
             0){              if(s+tr[p][r]>=m) break;                     vis[r]=1;            run(r,d+1,s+tr[p][r]);                vis[r]=0;        }        }        }    int main(){    scanf("%d",&n);        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                scanf("%d",&tr[i][j]);    vis[1]=1;    run(1,1,0);    printf("%d",m);    return 0;}
            
           
          

AC代码3：

#include
          
           #include
           
            #include
            
             using namespace std;int f[20],map[16*16][16*16];int n,a,b,c,sum=0x7f7f7f7f;void Dfs(int s ,int dis,int k){    f[s]=1;    if((dis+(n-k))>=sum) return;    if(k==n)     {        sum=min(sum,dis+map[s][1]);    }    for(int i=1;i<=n;i++)    {        if(f[i]==0)         {            Dfs(i,dis+map[s][i],k+1);            f[i]=0;        }            }}int main(){    cin>>n;    memset(f,0,sizeof f );        for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)          scanf("%d",&map[i][j]);    Dfs(1,0,1);                                                                    printf("%d",sum);                                                        return 0;}