首页 > 代码库 > POJ 3311 Hie with the Pie (状压DP)
POJ 3311 Hie with the Pie (状压DP)
状态压缩DP
dp[i][j]表示在i状态(用二进制表示城市有没有经过)时最后到达j城市的最小时间
转移方程dp[i][j]=min(dp[i][k]+d[k][j],dp[i][j])
d[k][j]是k城市到j城市的最短距离 要先用flody处理
#include<bits.stdc++.h> using namespace std; int d[20][20],dp[1<<11][20]; int n,m; void flody() { for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { if(d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j]; } } void DP() { int ans=INT_MAX; for(int i=0;i<(1<<n);i++) for(int j=1;j<=n;j++) { if(i==(1<<(j-1))) dp[i][j]=d[0][j]; else if(i&(1<<(j-1))) { dp[i][j]=INT_MAX; for(int k=1;k<=n;k++) if(k!=j&&(i&(1<<(k-1)))) dp[i][j]=min(dp[i^(1<<(j-1))][k]+d[k][j],dp[i][j]); } } for(int i=1;i<=n;i++) ans=min(ans,dp[(1<<n)-1][i]+d[i][0]); printf("%d\n",ans); } int main() { while(scanf("%d",&n)==1&&n) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&d[i][j]); flody(); DP(); } return 0; }
POJ 3311 Hie with the Pie (状压DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。