记录编号	357893	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.655 s
提交时间	2016-12-13 13:20:13	内存使用	62.92 MiB

#include<cstdio>
#include<algorithm>
#define INF 9999999
using namespace std;
int n,m,v,e;
int c[2010]={0},d[2010]={0},A[500][500]={0};
double k[2010]={0},F[2010][2010][2]={0};
void Floyd(){
	for(int k=1;k<=v;k++){
		for(int u=1;u<=v;u++){
			for(int q=1;q<=v;q++){
					if(A[u][q]>A[u][k]+A[k][q])
						A[u][q]=A[u][k]+A[k][q];
			}
		}
	}
}
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]);//噢卧槽，读入是"%lf",简直太蠢……
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++)
			A[i][j]=INF;
		A[i][i]=0;
	}
	for(int i=1;i<=e;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		A[a][b]=min(w,A[a][b]);
		A[b][a]=min(w,A[b][a]);
	}
	Floyd();
	double ans=0;
	F[1][0][1]=INF;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			double qwq=F[i-1][j][0]+A[c[i-1]][c[i]];
			double qaq=F[i-1][j][1]
			+(k[i-1]*A[d[i-1]][c[i]])
			+((1-k[i-1])*A[c[i-1]][c[i]]);
			F[i][j][0]=min(qwq,qaq);
			double abc=F[i-1][j-1][0]
				+(k[i]*A[c[i-1]][d[i]])
				+((1-k[i])*A[c[i-1]][c[i]]);
			double edf=F[i-1][j-1][1]
				+(k[i]*k[i-1]*A[d[i]][d[i-1]])
				+((1-k[i-1])*k[i]*A[c[i-1]][d[i]])
				+((1-k[i])*k[i-1]*A[d[i-1]][c[i]])
				+((1-k[i])*(1-k[i-1])*A[c[i-1]][c[i]]);
			F[i][j][1]=min(abc,edf);
		}
		F[i][0][0]=F[i-1][0][0]+A[c[i-1]][c[i]];
		F[i][0][1]=INF;
	}
	ans=min(F[n][m][0],F[n][m][1]);
	printf("%.2lf\n",ans);
	return 0;//DP大法好
}