首页 > 代码库 > 【CODEVS】2800 送外卖
【CODEVS】2800 送外卖
【算法】最短路(floyd)&&状态压缩型动态规划(DP)
【题解】dp的顺序应该是由含1的个数少的二进制到1的个数高的二进制(第一重循环)
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int inf=0x3f3f3f3f,maxn=18; int mp[maxn][maxn],f[maxn][(1<<maxn)],n; int main() { scanf("%d",&n);n++; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); 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++) if(mp[i][j]>mp[i][k]+mp[k][j])mp[i][j]=mp[i][k]+mp[k][j]; memset(f,0x3f,sizeof(f)); f[1][0]=0; for(int i=0;i<=(1<<n)-1;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) if(i&(1<<(j-1)))f[j][i]=min(f[j][i],f[k][i-(1<<(j-1))]+mp[k][j]); printf("%d",f[1][(1<<n)-1]); return 0; }
【CODEVS】2800 送外卖
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。