题目：换教室
思路：
dp。
先用floyd预处理出每两间教室的最短路。
状态 f[i][j][0/1] 表示 考虑前 i 个时间段，提交 j 次申请，第 j 次申请通过/不通过 的期望最短距离。
转移：
一、 当前教室不更换，此时
f[i][j][0]=min(f[i-1][j][0]+dist[c[i]][c[i-1]],f[i-1][j][1]+dist[c[i]][d[i-1]]*p[i-1]+dist[c[i]][c[i-1]]*(1-p[i-1]));
即分前一时间段申请通过，前一段时间申请且不通过 和前一段时间不申请讨论。
二、当前教室更换，此时
f[i][j][1]=min(f[i-1][j-1][0]+dist[d[i]][c[i-1]]*p[i]+dist[c[i]][c[i-1]]*(1-p[i]),f[i-1][j-1][1]+dist[d[i]][d[i-1]]*p[i]*p[i-1]+dist[c[i]][d[i-1]]*(1-p[i])*p[i-1]+dist[d[i]][c[i-1]]*p[i]*(1-p[i-1])+dist[c[i]][c[i-1]]*(1-p[i])*(1-p[i-1]));
即 前一段时间不申请 ， 此时申请通过 ；
前一段时间不申请，此时申请不通过；
前一段时间申请通过，此时申请通过；
前一段时间申请不通过，此时申请通过；
前一段时间申请通过，此时申请不通过；
前一段时间申请不通过，此时申请不通过。
注意初值，f[1][0][0]=f[1][1][1]=0 ，即第一间教室申请或不申请都不需要额外的花费距离。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 2000
#define maxv 300
#define read(x) scanf("%d",&x)
#define db double
#define readdb(x) scanf("%lf",&x)
#define inf (1e9)int n,m,v,e;
int c[maxn+5],d[maxn+5];
db p[maxn+5];int dist[maxv+5][maxv+5];db f[maxn+5][maxn+5][3];void readin() {
read(n),read(m),read(e),read(v);for(int i=1;i<=n;i++) read(c[i]);for(int i=1;i<=n;i++) read(d[i]);for(int i=1;i<=n;i++) readdb(p[i]);for(int i=1;i<=e;i++) for(int j=1;j<=e;j++) if(i!=j) dist[i][j]=inf;for(int i=1;i<=v;i++) {
int x,y,z;read(x),read(y),read(z);dist[x][y]=min(dist[x][y],z);dist[y][x]=min(dist[y][x],z);}
}void floyd() {
for(int k=1;k<=e;k++) {
for(int i=1;i<=e;i++) {
for(int j=1;j<=e;j++) {
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}}
}void dp() {
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=inf;f[1][0][0]=f[1][1][1]=0;for(int i=2;i<=n;i++) {
for(int j=0;j<=m;j++) {
f[i][j][0]=min(f[i-1][j][0]+dist[c[i]][c[i-1]],f[i-1][j][1]+dist[c[i]][d[i-1]]*p[i-1]+dist[c[i]][c[i-1]]*(1-p[i-1]));if(j!=0)f[i][j][1]=min(f[i-1][j-1][0]+dist[d[i]][c[i-1]]*p[i]+dist[c[i]][c[i-1]]*(1-p[i]),f[i-1][j-1][1]+dist[d[i]][d[i-1]]*p[i]*p[i-1]+dist[c[i]][d[i-1]]*(1-p[i])*p[i-1]+dist[d[i]][c[i-1]]*p[i]*(1-p[i-1])+dist[c[i]][c[i-1]]*(1-p[i])*(1-p[i-1]));}}
}int main() {
readin();floyd();dp();db ans=inf;for(int i=0;i<=m;i++) {
ans=min(ans,f[n][i][0]);ans=min(ans,f[n][i][1]);}printf("%.2lf",ans);return 0;
}