记录编号	474432	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	2.040 s
提交时间	2017-11-10 01:54:42	内存使用	62.80 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 1000000007
const int maxn=2005;
using namespace std;
int n,m,v,e;
int c[maxn],d[maxn];
double k[maxn],dp[maxn][maxn][2],dis[maxn][maxn];
int main()
{
	freopen("classrooma.in","r",stdin);
	freopen("classrooma.out","w",stdout);
	cin>>n>>m>>v>>e;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i<=n;i++)cin>>k[i];
	for(int i=0;i<=v;i++)
		for(int j=0;j<=v;j++)
			if(i==j)dis[i][j]=0;
			else dis[i][j]=INF;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			dp[i][j][0]=dp[i][j][1]=INF;
	dp[1][0][0]=dp[1][1][1]=0;
	for(int i=1;i<=e;i++)
	{
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		if(aa==bb)continue;
		if(cc<dis[aa][bb])dis[aa][bb]=cc;
		dis[bb][aa]=dis[aa][bb];
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
			for(int k=1;k<=v;k++)
				dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
	for(int i=2;i<=n;i++)
	{
		dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];
		for(int j=1;j<=min(i,m);j++)
		{
			double na,nb,nc,nd;
			na=dp[i-1][j][0]+dis[c[i-1]][c[i]];
			nb=dp[i-1][j][1]+(1.0-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]];
			dp[i][j][0]=min(na,nb);
			nc=dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]];
			nd=dp[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]+k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]];
			dp[i][j][1]=min(nc,nd);
		}
	}
	double ans=dp[n][0][0];
	for(int i=1;i<=m;i++)ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
	printf("%.2f\n",ans);
	return 0;
}