32pts

#include<bits/stdc++.h>
using namespace std;
const int N=2025;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
int a,b,w,m,n,v,e,c[N],d[N],dis[N][N];double k[N],f[N][N][2];
signed main(){
	n=read();m=read();v=read();e=read();
	for(int i=1;i<=n;i++) c[i]=read();
	for(int i=1;i<=n;i++) d[i]=read();
	for(int i=1;i<=n;i++) scanf("%lf",k+i) ;
	memset(dis,0x7f,sizeof(dis));
	memset(f,0x7f,sizeof(f));
	for(int i=1;i<=v;i++) dis[i][i]=0;
	for(int i=1;i<=e;i++){
		a=read();b=read();w=read();
		dis[a][b]=dis[b][a]=min(w,dis[a][b]);
	}
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
			for(int j=1;j<i;j++)
				if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
	f[1][0][0]=f[1][1][1]=0;
	for(int i=2;i<=n;i++){
		double del1=(double)dis[c[i-1]][c[i]];
		double del2=(double)dis[d[i-1]][c[i]];
		double del3=(double)dis[c[i-1]][d[i]];
		double del4=(double)dis[d[i-1]][d[i]];
		for(int j=0;j<=m;j++){
			f[i][j][0]=min(f[i-1][j][0]+del1,f[i-1][j][1]+del2*k[i-1]+del1*(1-k[i-1]));
			if(j) f[i][j][1]=min(f[i-1][j-1][0]+del3*k[i]+del1*(1-k[i]),f[i-1][j-1][1]+del1*(1-k[i-1])*(1-k[i])+del3*k[i]*(1-k[i-1])+del2*(1-k[i])*k[i-1]+del4*k[i]*k[i-1]);
		}
	}
	double ans=9999999999;
	for(int i=0;i<=m;i++) ans=min(f[n][i][0],min(ans,f[n][i][1]));
	printf("%0.2lf",ans);
	return 0;
}//f[i][j][0/1]表示第i个时段已经换了j次课本次不换/换的期望值 

100pts

#include<bits/stdc++.h>
using namespace std;
const int N=2004;
int a,b,w,n,m,e,v,c[N],d[N];
double k[N],f[N][N][2],dis[N][N];
inline double min(double a,double b){return a>b?b:a;}
int main(){
	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);	
	memset(dis,0x7f,sizeof(dis));
	memset(f,0x7f,sizeof(f));
	for(int i=1;i<=v;++i) dis[i][i]=0;		
	for(int i=1;i<=e;++i){
		scanf("%d%d%d",&a,&b,&w);
		dis[a][b]=dis[b][a]=min(w,dis[b][a]);
	}
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
    		for(int j=1;j<i;j++)
        		if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
	f[1][0][0]=f[1][1][1]=0;
	for(int i=2;i<=n;++i){
		double del1=dis[c[i-1]][c[i]];
		double del2=dis[d[i-1]][c[i]];
		double del3=dis[c[i-1]][d[i]];
		double del4=dis[d[i-1]][d[i]];
		for(int j=0;j<=m;++j){
			f[i][j][0]=min(f[i-1][j][0]+del1,f[i-1][j][1]+del2*k[i-1]+del1*(1-k[i-1]));
			if(j) f[i][j][1]=min(f[i-1][j-1][0]+del3*k[i]+del1*(1-k[i]),f[i-1][j-1][1]+del1*(1-k[i])*(1-k[i-1])+del3*(1-k[i-1])*k[i]+del2*(1-k[i])*k[i-1]+del4*k[i-1]*k[i]);
		}
	}
	double ans=9999999999;
    for(int i=0;i<=m;++i) ans=min(f[n][i][0],min(f[n][i][1],ans));
    printf("%.2lf",ans) ;
	return 0 ;
}