本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
Input
Output
Sample Input
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
Sample Output
24分
注意到有6个测试点m=0，则说明不能提出申请，那么只需要求出全图的两两之间的最短路，路径唯一确定。
52分
注意到另外有7个测试点m=1，只能提出一次申请。我们可以直接枚举在哪里提出申请，再与不申请的时候取一个min就可以了。
76分
注意到还有6个测试点m=2，只能提出两次申请，暴力枚举哪两个点申请即可。
80分
其实我们并不需要分那么多类情况讨论，考虑直接爆搜，在每个点是否提出申请，最后暴力计算贡献。因为这样的复杂度是C(n,m)的，所以m<=2和n<=10是完全没有问题的，直接可以用搜索拿到80分。
100分
这显然是一道概率DP裸题。考虑f[i][j][0、1]表示前i堂课，已经申请了j次，这次申不申请的最小期望值，则：
$${f[i][j][0]=min( f[i-1][j][0]+dis(c[i-1],c[i])，f[i-1][j][1]+dis(c[i-1],c[i])*(1-p[i-1])+dis(d[i-1],c[i])*p[i] )}$$
$${f[i][j][1]=min( f[i-1][j-1][0]+dis(c[i-1],d[i])*p[i]+dis(c[i-1],c[i])*(1-p[i]),f[i-1][j-1][1]+dis(c[i-1],c[i])*(1-p[i-1])*(1-p[i])+dis(c[i-1],d[i])*(1-p[i-1])*p[i]+dis(d[i-1],c[i])*p[i-1]*(1-p[i]))+dis(d[i-1],d[i])*p[i-1]*p[i]) }$$
（dis(i,j)表示i到j的最短距离）
需要说明的是，期望是可以线性相加的，也就是说一条路径上的距离总期望值实际上就等于每两个相邻点之间的距离的期望值的总和。另外上面的转移式可以这样理解：在我们已经提出申请的情况下，对于所有情况的讨论就是在现有的申请情况下的能得到的距离期望值，事实上是根据计算了每条边的贡献。
这样即可获得满分。时间复杂度：O(V3+nm)
注意事项
如果状态的0、1表示的是地点在c还是d的话会有不少问题，因为压根就不能体现出申请的时候的成功与失败结果，但是对于m<=2的点基本不会出错，大点的出错概率也不是特别大，就导致这样完全错误的状态设计在联赛数据下获得了88分……
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXD = ;
const int inf = (<<);
int n,m,D,bian,c[MAXN],d[MAXN],dis[MAXD][MAXD];
double f[MAXN][MAXN][],k[MAXN],ans; inline int getint(){
int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();
if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;
} inline void work(){
n=getint(); m=getint(); D=getint(); bian=getint(); int x,y,z,lim; double minl;
for(int i=;i<=n;i++) c[i]=getint(); for(int i=;i<=n;i++) d[i]=getint(); for(int i=;i<=n;i++) scanf("%lf",&k[i]);
for(int i=;i<=D;i++) for(int j=;j<=D;j++) dis[i][j]=inf;
for(int i=;i<=bian;i++) {
x=getint(); y=getint(); z=getint(); if(dis[x][y]==inf) dis[x][y]=dis[y][x]=z;
else dis[x][y]=min(dis[x][y],z),dis[y][x]=dis[x][y];
}
for(int l=;l<=D;l++) for(int i=;i<=D;i++) if(i!=l) for(int j=;j<=D;j++) if(j!=l&&i!=j) dis[i][j]=min(dis[i][l]+dis[l][j],dis[i][j]);
for(int i=;i<=n;i++) for(int j=;j<=m;j++) f[i][j][]=f[i][j][]=1e30; f[][][]=f[][][]=;
for(int i=;i<=D;i++) dis[i][i]=;
for(int i=;i<=n;i++) {
lim=min(i,m);
for(int j=;j<=lim;j++) {
minl=f[i-][j][]+dis[c[i-]][c[i]]*(1.0-k[i-])+dis[d[i-]][c[i]]*k[i-];
minl=min(minl,f[i-][j][]+dis[c[i-]][c[i]]);
f[i][j][]=min(f[i][j][],minl);
if(j>=) {
minl=f[i-][j-][]+dis[c[i-]][c[i]]*(1.0-k[i])*(1.0-k[i-])+dis[c[i-]][d[i]]*(1.0-k[i-])*k[i];
minl+=dis[d[i-]][c[i]]*k[i-]*(-k[i])+dis[d[i-]][d[i]]*k[i-]*k[i];
minl=min(minl,f[i-][j-][]+dis[c[i-]][d[i]]*k[i]+dis[c[i-]][c[i]]*(1.0-k[i]));
f[i][j][]=min(f[i][j][],minl);
}
}
}
ans=1e30; for(int i=;i<=m;i++) ans=min(ans,min(f[n][i][],f[n][i][]));
printf("%.2lf",ans);
} int main()
{
work();
return ;
}