社区讨论

求助!!!哪里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 条回复,欢迎继续交流。

正在加载回复...