首页 > 代码库 > 【动态规划+Floyd】OpenJudge3368
【动态规划+Floyd】OpenJudge3368
OpenJudge上刷水都不会了……这题居然写了一个半小时……
【题目大意】
诸葛亮要征服N城市。然而,City-X在击败City-2,City-3……City-x-1后击败。关羽,张飞,赵云,每个人都应该领导一个军队。三个军队从City-0出发,征服所有的城市。求三个军队的行程总长的最小值。
【思路】
首先求出最短路径。我们用dp[i][j][k]表示当前三个部队分别位于i、j、k时的答案(j<=k<=i)。分别考虑从i、j、k中的一支部队走到i+1的情况，总共三个递推式。
对于返回，直接假设他们都走到最终状态后统一返回，就是从0到最终状态的最短路径就可以了。
哦对了，i要开滚动。
【错误点】
不要忘记滚动数组每次都要重新初始化！好像是第二次犯下这个错误了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long ll; 8 const int MAXN=505; 9 int n,m;10 int dis[MAXN][MAXN],dist[MAXN][MAXN];11 int dp[2][MAXN][MAXN];12 13 14 void init()15 {16 scanf("%d%d",&n,&m);17 memset(dist,0x3f,sizeof(dist));18 for (int i=1;i<=m;i++)19 {20 int u,v,w;21 scanf("%d%d%d",&u,&v,&w);22 dist[u][v]=dist[v][u]=min(dist[u][v],w);23 }24 for (int i=0;i<=n;i++) dist[i][i]=0;25 for(int k=0;k<=n;++k)26 for(int i=0;i<=n;++i)27 for(int j=0;j<=n;++j)28 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);29 }30 31 void solve()32 {33 int cur=0;34 memset(dp,0x3f,sizeof(dp));35 ll ans=1<<29;36 dp[cur][0][0]=0;37 for(int i=0;i<n;++i)38 {39 cur^=1;40 memset(dp[cur],0x3f,sizeof(dp[cur]));//注意每次滚动数组都要清成无穷大,i=3的时候dp[0][0][0]!=041 for(int j=0;j<=i;++j)42 for(int k=j;k<=i;++k)43 {44 dp[cur][j][k]=min(dp[cur][j][k],dp[1-cur][j][k]+dist[i+1][i]);45 dp[cur][k][i]=min(dp[cur][k][i],dp[1-cur][j][k]+dist[j][i+1]);46 dp[cur][j][i]=min(dp[cur][j][i],dp[1-cur][j][k]+dist[k][i+1]);47 if (i==n-1) 48 {49 ans=min(ans,(ll)dp[cur][j][k]+(ll)dist[0][n]+(ll)dist[0][j]+(ll)dist[0][k]);50 ans=min(ans,(ll)dp[cur][k][i]+(ll)dist[0][n]+(ll)dist[0][k]+(ll)dist[0][i]);51 ans=min(ans,(ll)dp[cur][j][i]+(ll)dist[0][n]+(ll)dist[0][j]+(ll)dist[0][i]);52 }53 }54 }55 cout<<ans<<endl;56 }57 58 int main()59 {60 init();61 solve();62 return 0;63 }
【动态规划+Floyd】OpenJudge3368
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。