首页 > 其他 > 详细

【CODEVS】2800 送外卖

时间:2017-03-05 14:17:20      阅读:187      评论:0      收藏:0      [点我收藏+]

【算法】状态压缩型动态规划

【题解】http://blog.csdn.net/harryguo2012/article/details/42175559(初始不算经过起点1的话,答案就是f[1][(1<<n)-1])

先跑一遍floyd后就不用再纠结重复经过的问题了!!!

然后就转化为经典状压问题。

技术分享
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=20;
int n,mp[maxn][maxn],f[maxn][70010];
int main()
{
    scanf("%d",&n);n++;
    int x;
    for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=n;j++)
          {
              scanf("%d",&x);
              mp[i][j]=x;
          }
     }
    for(int i=1;i<=n;i++)mp[i][i]=0;
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int k=1;k<=(1<<n)-1;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       if((1<<(i-1))&k)f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+mp[j][i]);
    printf("%d",f[1][(1<<n)-1]);
    return 0;
}
View Code

 

【CODEVS】2800 送外卖

原文:http://www.cnblogs.com/onioncyc/p/6505203.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!