80pts

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
int n,m,N,M;
int a[2010],b[2010];
double p[2010];
int g[310][310];
double f[2010][2010][3];
//f表示前i节课申请换j次，第i节课没申请/申请没过/申请通过的最小期望
int main()
{
	cin>>n>>m>>N>>M;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>p[i];
	memset(g,999999,sizeof(g));
	for(int i=1;i<=N;i++)g[0][i]=g[i][0]=g[i][i]=0;
	for(int i=1;i<=M;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		g[x][y]=g[y][x]=min(g[x][y],w);
	}
	for(int k=1;k<=N;k++)
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			f[i][j][0]=min(f[i-1][j][0]+g[a[i-1]][a[i]],p[i-1]*(f[i-1][j][2]+g[b[i-1]][a[i]])+(1-p[i-1])*(f[i-1][j][1]+g[a[i-1]][a[i]]));
			if(j)
			{
                f[i][j][1]=min(f[i-1][j-1][0]+g[a[i-1]][a[i]],p[i-1]*(f[i-1][j-1][2]+g[b[i-1]][a[i]])+(1-p[i-1])*(f[i-1][j-1][1]+g[a[i-1]][a[i]]));
                f[i][j][2]=min(f[i-1][j-1][0]+g[a[i-1]][b[i]],p[i-1]*(f[i-1][j-1][2]+g[b[i-1]][b[i]])+(1-p[i-1])*(f[i-1][j-1][1]+g[a[i-1]][b[i]]));
			}
            else f[i][j][1]=f[i][j][2]=1e9;
		}
	printf("%.2lf\n",min(f[n][m][0],p[n]*f[n][m][1]+(1-p[n])*f[n][m][2]));
	return 0;
}

顺便吐槽测试点顺序都是乱的