先用Floyd把最短路处理一遍，接下来就是重头戏了
用 f [ i ][ j ][ 0/1 ] 表示在第 i 个时间段，发出了 j 次申请（注意不一定成功），并且在这个时间段是否（1/0）申请换了教室
需要知道的一点是：既然是期望，我们求的就是边权*概率（P4316 绿豆蛙的归宿）的和
同样的，在这题中，我们需要求的是，可转移的状态（d [ i ][ j ]）*概率之和。
既然是求最小期望，那么我们只要求从第 1->n 个时间段中可以转移的最短（期望）路径，统计这条路径上的期望即可
所以列出状态转移方程（详见代码），解决qwq
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
inline int Int(){
char c=getchar(); int x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
return x;
}
inline int min1(const int &a,const int &b) {return a<b? a:b;}
inline double min2(const double &a,const double &b) {return a<b ?a:b;} int n,m,v,e,a[],b[],d[][];
double c[],f[][][]; int main(){
n=Int(); m=Int(); v=Int(); e=Int();
for(int i=;i<=n;++i) a[i]=Int();
for(int i=;i<=n;++i) b[i]=Int();
for(int i=;i<=n;++i) scanf("%lf",&c[i]); memset(d,,sizeof(d));
int q1,q2,q3;
for(int i=;i<=e;++i){
q1=Int(); q2=Int(); q3=Int();
d[q1][q2]=d[q2][q1]= d[q1][q2]<q3 ? d[q1][q2]:q3;
}
for(int k=;k<=v;++k)
for(int i=;i<=v;++i)
for(int j=;j<=v;++j)
d[i][j]=min1(d[i][j],d[i][k]+d[k][j]);
for(int i=;i<=v;++i) d[i][i]=;
//Floyd最短路
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
f[i][j][]=f[i][j][]=;
f[][][]=f[][][]=;
for(int i=;i<=n;++i) //对于每一种状态进行转移：找到一种期望最小、可以转移过来的状态
{
f[i][][]=f[i-][][]+d[a[i-]][a[i]];
for(int j=;j<=m;++j)
{
f[i][j][]=min2(f[i][j][],f[i-][j][]
+(double)d[a[i-]][a[i]]); //这次和上次都不申请
f[i][j][]=min2(f[i][j][],f[i-][j][]
+(double)d[b[i-]][a[i]]*c[i-] //这次不申请，上次申请成功
+(double)d[a[i-]][a[i]]*(1.0-c[i-])); //这次不申请，上次申请失败
f[i][j][]=min2(f[i][j][],f[i-][j-][]
+(double)d[a[i-]][b[i]]*c[i] //这次申请成功，上次不申请
+(double)d[a[i-]][a[i]]*(1.0-c[i])); //这次申请失败，上次不申请
f[i][j][]=min2(f[i][j][],f[i-][j-][]
+(double)d[b[i-]][b[i]]*c[i-]*c[i] //这次和上次都申请成功
+(double)d[a[i-]][b[i]]*(1.0-c[i-])*c[i] //这次申请成功，上次申请失败
+(double)d[b[i-]][a[i]]*c[i-]*(1.0-c[i]) //这次申请失败，上次申请成功
+(double)d[a[i-]][a[i]]*(1.0-c[i-])*(1.0-c[i])); //这次和上次都申请失败
}
}
double ans=100000000.00;
for(int i=;i<=m;++i) ans=min2(ans,min2(f[n][i][],f[n][i][])); //扫一遍找最小期望
printf("%.2lf",ans);
return ;
}