概率期望\(dp\).

首先随便用个啥处理出任意两点之间的最短路。

设\(f[i][j][0/1]\)表示前\(i\)个时间段申请换了\(j\)次教室的期望最小值，\(0/1\)记录第\(i\)次有没有换教室。

然后枚举前两维，分情况讨论下这次和上次有没有申请换教室，申请的有没有成功。

转移方程就很显然了。

\[ 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.0-p[i-1])+dis[d[i-1]][c[i]]*p[i-1]); \]

申请了换教室的情况也类似，方程太长就不写了。

#pragma GCC optimize(3)#include
    
     using namespace std;#define read(x) scanf("%d",&x)#define write(x) printf("%d\n",x)#define maxn 2005int n,m,v,e,c[maxn],d[maxn],mp[305][305];double f[maxn][maxn][2],p[maxn];int main(){    //freopen("testdata.in","r",stdin);    //freopen("out.out","w",stdout);    read(n),read(m),read(v),read(e);int x,y,z;    for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) mp[i][j]=1e9;    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++) scanf("%lf",&p[i]);    for(int i=1;i<=e;i++) read(x),read(y),read(z),mp[x][y]=mp[y][x]=min(mp[x][y],z);    for(int k=1;k<=v;k++)     for(int i=1;i<=v;i++)        for(int j=1;j