记录编号	354852	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.938 s
提交时间	2016-11-23 13:08:10	内存使用	60.46 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int V=510,N=2010;
int n,m,v,e,dis[V][V],c[N],d[N];
double k[N],g[N],dp[N][N][2];
int main()
{
	freopen("classrooma.in","r",stdin);
	freopen("classrooma.out","w",stdout);
	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]),g[i]=1-k[i];
	for (int i=1;i<=v;i++)
	for (int j=1;j<=v;j++)
	if (i!=j) dis[i][j]=1e9;
	for (int i=1;i<=e;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		dis[u][v]=dis[v][u]=min(dis[u][v],l);
	}
	for (int k=1;k<=v;k++)
	for (int i=1;i<=v;i++)
	for (int j=1;j<=v;j++)
		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for (int i=1;i<=n;i++)
	for (int j=0;j<=m;j++)
	for (int a=0;a<2;a++)
		dp[i][j][a]=1e16;
	dp[1][0][0]=dp[1][1][1]=0;
	for (int i=1;i<n;i++)
	for (int j=0;j<=m;j++){//已经使用多少次机会 
		int l1=dis[c[i]][c[i+1]],l2=dis[d[i]][c[i+1]],l3=dis[c[i]][d[i+1]],l4=dis[d[i]][d[i+1]];
		double v0=dp[i][j][0],v1=dp[i][j][1];
		dp[i+1][j][0]=min(dp[i+1][j][0],v0+l1);
		dp[i+1][j][0]=min(dp[i+1][j][0],v1+l1*g[i]+l2*k[i]);
		if (j<m){
			dp[i+1][j+1][1]=min(dp[i+1][j+1][1],v0+l1*g[i+1]+l3*k[i+1]);
			dp[i+1][j+1][1]=min(dp[i+1][j+1][1],v1+l1*g[i]*g[i+1]+l2*k[i]*g[i+1]+l3*g[i]*k[i+1]+l4*k[i]*k[i+1]);
		}
	}
	double ans=1e16;
	for (int i=0;i<=m;i++)
	for (int a=0;a<2;a++)
		ans=min(ans,dp[n][i][a]);
	printf("%.2lf\n",ans);
	return 0;
}