社区讨论
求助!!!哪里wa了??
P1850[NOIP 2016 提高组] 换教室参与者 2已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xq9tf
- 此快照首次捕获于
- 2025/11/20 12:32 4 个月前
- 此快照最后确认于
- 2025/11/20 15:21 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,v,e,a,b;
int c[2005],d[2005];
double dis[305][305],k[2005],dp[2005][2005][2],ans=9999999999999.00000,w;
void init()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=v;i++)
for(int j=1;j<i;j++)
dis[i][j]=dis[j][i]=999999999;
for(int i=1;i<=n;++i) scanf("%d",&c[i]);
for(int i=1;i<=n;++i) scanf("%d",&d[i]);
for(int i=1;i<=n;++i) scanf("%lf",&k[i]);
while(e--)
{
scanf("%d%d%lf",&a,&b,&w);
dis[a][b]=min(w,dis[a][b]);dis[b][a]=dis[a][b];
}
}
void floyed()
{
for(int k=1;k<=v;++k)
for(int i=1;i<=v;++i)
for(int j=1;j<i;++j)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
}
}
void solve()
{
for(int i=2;i<=n;++i)
for(int j=0;j<=min(i,m);++j)
{
if(j==0) dp[i][j][0]=dp[i-1][j][0]+dis[c[i]][c[i-1]];
else
{
dp[i][j][0]=min(dp[i-1][j][0]+(double)dis[c[i-1]][c[i]],dp[i-1][j][1]+k[i-1]*(double)dis[d[i-1]][c[i]]+(1.000000-k[i-1])*(double)dis[c[i-1]][c[i]]);
if(j>1)
dp[i][j][1]=min(dp[i-1][j-1][0]+(double)dis[c[i-1]][d[i]]*k[i]+(1.000000-k[i])*(double)dis[c[i-1]][c[i]],dp[i-1][j-1][1]+k[i]*k[i-1]*(double)dis[d[i-1]][d[i]]+k[i]*(1.000000-k[i-1])*(double)dis[d[i]][c[i-1]]+(1.000000-k[i])*k[i-1]*(double)dis[d[i-1]][c[i]]+(1.000000-k[i])*(1.000000-k[i-1])*(double)dis[c[i]][c[i-1]]);
else
dp[i][j][1]=dp[i-1][j-1][0]+(double)dis[c[i-1]][d[i]]*k[i]+(1.000000-k[i])*(double)dis[c[i-1]][c[i]];
}
//printf("%lf %lf\n",dp[i][j][0],dp[i][j][1]);
if(i==n)
{
if(j!=0)
ans=min(ans,min(dp[i][j][1],dp[i][j][0]));
else
ans=min(ans,dp[i][j][0]);
}
}
printf("%.2lf",ans);
}
int main()
{
init();
floyed();
solve();
return 0;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...