【动态规划+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要开滚动。

【错误点】

不要忘记滚动数组每次都要重新初始化!好像是第二次犯下这个错误了。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int MAXN=;
int n,m;
int dis[MAXN][MAXN],dist[MAXN][MAXN];
int dp[][MAXN][MAXN]; void init()
{
scanf("%d%d",&n,&m);
memset(dist,0x3f,sizeof(dist));
for (int i=;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
dist[u][v]=dist[v][u]=min(dist[u][v],w);
}
for (int i=;i<=n;i++) dist[i][i]=;
for(int k=;k<=n;++k)
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
} void solve()
{
int cur=;
memset(dp,0x3f,sizeof(dp));
ll ans=<<;
dp[cur][][]=;
for(int i=;i<n;++i)
{
cur^=;
memset(dp[cur],0x3f,sizeof(dp[cur]));//注意每次滚动数组都要清成无穷大,i=3的时候dp[0][0][0]!=0
for(int j=;j<=i;++j)
for(int k=j;k<=i;++k)
{
dp[cur][j][k]=min(dp[cur][j][k],dp[-cur][j][k]+dist[i+][i]);
dp[cur][k][i]=min(dp[cur][k][i],dp[-cur][j][k]+dist[j][i+]);
dp[cur][j][i]=min(dp[cur][j][i],dp[-cur][j][k]+dist[k][i+]);
if (i==n-)
{
ans=min(ans,(ll)dp[cur][j][k]+(ll)dist[][n]+(ll)dist[][j]+(ll)dist[][k]);
ans=min(ans,(ll)dp[cur][k][i]+(ll)dist[][n]+(ll)dist[][k]+(ll)dist[][i]);
ans=min(ans,(ll)dp[cur][j][i]+(ll)dist[][n]+(ll)dist[][j]+(ll)dist[][i]);
}
}
}
cout<<ans<<endl;
} int main()
{
init();
solve();
return ;
}
上一篇:ASP.NET MVC 中应用Windows服务以及Webservice服务开发分布式定时器


下一篇:浅谈SQL中的单引号