社区讨论

请大佬看一下哪里wa了

P1850[NOIP 2016 提高组] 换教室参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6xoyde
此快照首次捕获于
2025/11/20 12:31
4 个月前
此快照最后确认于
2025/11/20 12:31
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()
{
	for(int i=1;i<=v;i++)
	 for(int j=1;j<=v;j++)
	  dis[i][j]=999999999.000000;
	for(int i=0;i<=v;++i) dis[i][i]=0;
	scanf("%d%d%d%d",&n,&m,&v,&e);
	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]=w;dis[b][a]=w;
	}
}
void floyed()
{
	for(int i=1;i<=v;++i)
	 for(int j=1;j<=v;++j)
	 {
	 	if(i==j) continue;
	  for(int k=1;k<=v;++k)
	  {
	  	if(k==i||k==j) continue;
	  	if(dis[i][j]>dis[i][k]+dis[k][j])
	  	 dis[i][j]=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;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...