调了好几天还是92pts......这不珂学
查看原帖
调了好几天还是92pts......这不珂学
290095
UKE_自动机楼主2020/9/28 19:57

调的精神都出了点问题

用了各种玄学方法都A不掉......

求大佬指点QWQ

#include<bits/stdc++.h>
using namespace std;
int c[2010],d[2010];
double Map[2010][2010],k[2010],f[2010][310][2];
int n,m,v,e,c1,c2,c3,c4;
double ans=0x7f7f7f7f;
inline double min(double a,double b){
    return a<b?a:b;
}
int main()
{
	cin>>n>>m>>v>>e;
	for(register int i=1;i<=v;i++)
	{
		for(register int j=1;j<i;j++) Map[i][j]=Map[j][i]=ans;
	}
	for(register int i=1;i<=n;i++) cin>>c[i];
	for(register int i=1;i<=n;i++) cin>>d[i];
	for(register int i=1;i<=n;i++) cin>>k[i];
	for(register int i=1;i<=n;i++)
	{
		Map[i][i]=Map[i][0]=Map[0][i]=0;
	}
	for(register int i=1;i<=e;i++)
	{
		int a,b;
		double w;
		cin>>a>>b>>w;
		Map[a][b]=Map[b][a]=min(w,Map[a][b]);
	}
	for(register int z=1;z<=v;z++)
	{
		for(register int i=1;i<=v;i++)
		{    
			for(register int j=1;j<=v;j++)
			{
			 	Map[i][j]=min(Map[i][j],Map[i][z]+Map[z][j]);
	 		}
	 	}
	}
	for(register int i=0;i<=n;i++)
	{
		for(register int j=0;j<=m;j++)
		{
			for(register int z=0;z<=1;z++)
			{
				f[i][j][z]=ans;
			}
		}
	}
	f[1][0][0]=f[1][1][1]=0;
	for(register int i=2;i<=n;i++)
	{
		f[i][0][0]=f[i-1][0][0]+Map[c[i]][c[i-1]];
		for(register int j=0;j<=m;j++)
		{
			c1=c[i-1],c2=d[i-1],c3=c[i],c4=d[i];
			f[i][j][0]=min(f[i-1][j][0]+Map[c1][c3],f[i-1][j][1]+Map[c1][c3]*(1-k[i-1])+Map[c2][c3]*k[i-1]);
			if(j!=0) f[i][j][1]=min(f[i-1][j-1][0]+Map[c1][c3]*(1-k[i])+Map[c1][c4]*k[i],f[i-1][j-1][1]+Map[c2][c4]*k[i]*k[i-1]+Map[c2][c3]*k[i-1]*(1-k[i])+Map[c1][c4]*k[i]*(1-k[i-1])+Map[c1][c3]*(1-k[i-1])*(1-k[i]));
		}
	}
	for(register int i=0;i<=m;i++)
	{
		ans=min(f[n][i][0],min(f[n][i][1],ans));
	}
	printf("%.2f",ans);
	return 0;
}
2020/9/28 19:57
加载中...