期望dp,首先用floyd算法枚举每个点作为拐点，求出每两间教室之间的最短距离，然后设置状态dp[i][j][k]表示上了i节课换了j次教室，k表示当前课换没换教室，在转移时，如果当前课没换，只要考虑前一节课有没有换，换了有没有成功，如果当前课换了教室，要考虑上一节课换没换，换了成没成功和当前课成没成功

#include<bits/stdc++.h>
using namespace std;
int n, m, v, e;
const int N = 2005;
int ma[305][505];
int c[N][N];
double k[N];
double dp[N][N][2];
const double INF = 1e9;
int main()
{
	scanf("%d%d%d%d", &n, &m, &v, &e);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &c[i][0]);//安排上课的教室
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &c[i][1]);//可供选择的教室
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%lf", &k[i]);//更换教室的成功率
	}
	memset(ma, 63, sizeof ma);
	for (int i = 1; i <= e; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);//从u到v有一条长为w的路
		ma[u][v] = ma[v][u] = min(ma[u][v], w);//同样两个点可能有多条路
	}
	for (int k = 1; k <= v; k++)
	{
		for (int i = 1; i <= v; i++)
		{
			for (int j = 1; j <= v; j++)
			{
				ma[i][j] = min(ma[i][j], ma[i][k] + ma[k][j]);
				//floyd算法，枚举每个点作为拐点，求出每两个点之间的最短路
			}
		}
	}
	for (int i = 1; i <= v; i++)
	{
		ma[i][i]  = 0;//同教室间路线长度为0
	}
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			dp[i][j][0] = dp[i][j][1] = INF;
		}//求最小值，先把所有值初始化成最大
	}
	dp[1][0][0] = dp[1][1][1] = 0;
	for (int i = 2; i <= n; i++)
	{
		dp[i][0][0] = dp[i - 1][0][0] + ma[c[i - 1][0]][c[i][0]];
		//不换教室的话，期望就是上一时间段没换教室加上个教室到这个教室的距离
		for (int j = 1; j <= min(i, m); j++)
		{
			int o1 = c[i - 1][0], o2 = c[i - 1][1], o3 = c[i][0], o4 = c[i][1];
			dp[i][j][0] = min(dp[i - 1][j][0] + ma[o1][o3], dp[i - 1][j][1] + ma[o2][o3] * k[i - 1] + ma[o1][o3] * (1 - k[i - 1]));
			//这次没换的期望就是上一次没换，或者上一次换了且成功，或者上一次换了但没成功
			dp[i][j][1] = min(dp[i - 1][j - 1][0] + ma[o1][o4] * k[i] + ma[o1][o3] * (1 - k[i]), dp[i - 1][j - 1][1] + ma[o2][o3] * k[i - 1] * (1 - k[i]) + ma[o1][o3] * (1 - k[i - 1]) * (1 - k[i]) + ma[o1][o4] * (1 - k[i - 1]) * k[i] + ma[o2][o4] * k[i - 1] * k[i]);
			//这次换了的期望就是上一次没换且这次换失败了，或者上一次没换但这次换成功了
			//或者上一次换了没成功但这次成功了，或者上一次换了没成功这次也成功
			//或者上一次换了成功了但这次没成功，或者上一次换了没成功但这次成功了
		}		
	}
	double ans = INF;
	for (int i = 0; i <= m; i++)
	{
		ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
	}
	printf("%.2lf", ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,v,e,k,s,t,a[305][305],c[2005],d[2005],k1,k2,k3,k4;
//c上课教室 d另一间教室 
double f[2005][2005][2],p[2005];
//p申请通过概率 
int main(){
	freopen("in.txt","r",stdin);
	//freopen("out.txt","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>>p[i];
	memset(a,0x3f,sizeof(a));
	for (int i=1;i<=e;++i){
		cin>>s>>t>>k;
		a[s][t]=a[t][s]=min(a[s][t],k);
	}
	for (int i=1;i<=v;++i)
		a[i][i]=0;
	//floyd求最短路 
	for (int k=1;k<=v;++k)
		for (int i=1;i<=v;++i)
			for (int j=1;j<=v;++j)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	//初始化 
	for (int i=0;i<=n;++i)
		for (int j=0;j<=m;++j)
			f[i][j][0]=f[i][j][1]=1000000000000;
	f[1][0][0]=0;f[1][1][1]=0;
	//dp过程 
	for (int i=2;i<=n;++i)
		for (int j=0;j<=min(i,m);++j){
			k1=c[i-1];k2=d[i-1];k3=c[i];k4=d[i];
			f[i][j][0]=min(f[i-1][j][0]+a[k1][k3],f[i-1][j][1]+p[i-1]*a[k2][k3]+(1-p[i-1])*a[k1][k3]);
			//特判j>0才能转移 
			if (j>0) f[i][j][1]=min(f[i-1][j-1][0]+p[i]*a[k1][k4]+(1-p[i])*a[k1][k3],f[i-1][j-1][1]+
			p[i-1]*p[i]*a[k2][k4]+(1-p[i-1])*p[i]*a[k1][k4]+p[i-1]*(1-p[i])*a[k2][k3]+(1-p[i-1])*(1-p[i])*a[k1][k3]);
		}
	double ans=100000000000000;
	//求答案 
	for (int i=0;i<=m;++i){
		ans=min(ans,f[n][i][0]);
		if (i) ans=min(ans,f[n][i][1]);
	}
	printf("%.2f\n",ans);
}