记录编号	512395	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.578 s
提交时间	2018-10-03 17:24:22	内存使用	65.20 MiB

#include<iostream>  
#include<cstdio>
#include<cmath>
#include<cstring>  
#include<algorithm>  
using namespace std; 
int n,m,x[2010],y[2010],a1,a2,a3,mp[310][310],ds,bs;
double p[2010],f[2010][2010][2],ans=999999;
int main(){
    freopen("classrooma.in","r",stdin);        
    freopen("classrooma.out","w",stdout);	
	scanf("%d%d%d%d",&n,&m,&ds,&bs);
	for(int i=1;i<=ds;i++)
		for(int j=1;j<=ds;j++)	
			if(i!=j)
				mp[i][j]=999999;
	for(int i=1;i<=ds;i++)mp[i][i]=0;
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	for(int i=1;i<=n;i++)scanf("%d",&y[i]);
	for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
	for(int i=1;i<=bs;i++){
	    scanf("%d%d%d",&a1,&a2,&a3);
		mp[a1][a2]=min(mp[a1][a2],a3);
		mp[a2][a1]=mp[a1][a2];
	}
	for(int k=1;k<=ds;k++)
		for(int i=1;i<=ds;i++)
			for(int j=1;j<=ds;j++)
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
    f[1][0][1]=999999.0;
	for(int i=2;i<=n;i++){
	    for(int j=1;j<=m;j++){
			f[i][j][0]=min(f[i-1][j][0]+mp[x[i-1]][x[i]],f[i-1][j][1]+p[i-1]*mp[y[i-1]][x[i]]+(1.0-p[i-1])*mp[x[i-1]][x[i]]);
			f[i][j][1]=min(f[i-1][j-1][0]+p[i]*mp[x[i-1]][y[i]]+(1.0-p[i])*mp[x[i-1]][x[i]],f[i-1][j-1][1]+p[i-1]*p[i]*mp[y[i-1]][y[i]]+p[i-1]*(1.0-p[i])*mp[y[i-1]][x[i]]+(1.0-p[i-1])*p[i]*mp[x[i-1]][y[i]]+(1.0-p[i-1])*(1.0-p[i])*mp[x[i-1]][x[i]]);
			
		}
		f[i][0][0]=f[i-1][0][0]+mp[x[i-1]][x[i]];
		f[i][0][1]=999999.0;
	}
	printf("%.2lf",min(f[n][m][0],f[n][m][1]));
    return 0;  
}