我们令 \(f_{i,j,0/1}\) 表示前 \(i\) 个时间点，共申请了 \(j\) 次，第 \(i\) 个时间点是否 (\(1/0\)) 进行了申请，\(g_{i,j}\) 表示 \(i\to j\) 的最短路，\(p_i\) 表示原题中的 \(k_i\)
那么我们需要分情况讨论：
一、当前教室没有申请
如果前一教室有申请：\(f[i][j][0]=min(f[i−1][j][1]\)
(1) 成功：\(+p[i−1]\cdots dis[d[i−1]][c[i]]\)
(2) 失败：\(+(1−p[i−1])\cdots dis[c[i−1]][c[i]]\)
如果前一教室没有申请：\(f[i−1][j][0]\)，一定是前后均失败：\(+dis[c[i−1]][c[i]])\)
二、当前教室有申请
如果前一教室有申请：\(f[i][j][1]=min(f[i−1][j−1][1]\)
(1) 前后均成功：\(+p[i−1]\cdots p[i]\cdots dis[d[i−1]][d[i]]\)
(2) 前成功、后失败：\(+p[i−1]\cdots (1−p[i])\cdots dis[d[i−1]][c[i]]\)
(3) 前失败、后成功：\(+(1−p[i−1])\cdots p[i]\cdots dis[c[i−1]][d[i]]\)
(4) 前后均失败：\(+(1−p[i−1])\cdots (1−p[i])\cdots dis[c[i−1]][c[i]]\)
如果前一教室没有申请：\(f[i−1][j−1][0]\)，
(1) 后成功：\(+p[i]\cdots dis[c[i−1]][d[i]]\)
(2) 后失败：\(+(1−p[i])\cdots dis[c[i−1]][c[i]])\)
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define cmin(x,y) y<x?x=y:x=x;
const int N=2e3+5;
const int inf=1e9;
int n,m,V,E;
int c[N],d[N];
double p[N],g[N][N],f[N][N][2];
signed main(){
cin>>n>>m>>V>>E;
for(int i=1;i<=n;++i) cin>>c[i];
for(int i=1;i<=n;++i) cin>>d[i];
for(int i=1;i<=n;++i) cin>>p[i];
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
g[i][j]=(i!=j)*inf;
while(E--){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=g[y][x]=min(g[x][y],1.0*z);
}
for(int k=1;k<=V;++k)
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
if(i!=j&&j!=k&&i!=k)
g[i][j]=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]=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<=min(m,i);++j){
cmin(f[i][j][0],f[i-1][j][0]+g[c[i-1]][c[i]]);
cmin(f[i][j][0],f[i-1][j][1]+g[d[i-1]][c[i]]*p[i-1]+g[c[i-1]][c[i]]*(1-p[i-1]));
if(j){
cmin(f[i][j][1],f[i-1][j-1][0]+g[c[i-1]][d[i]]*p[i]+g[c[i-1]][c[i]]*(1-p[i]));
cmin(f[i][j][1],f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+g[c[i-1]][d[i]]*
(1-p[i-1])*p[i]+g[d[i-1]][c[i]]*(1-p[i])*p[i-1]+g[d[i-1]][d[i]]*p[i-1]*p[i]);
}
}
}
double ans=inf;
for(int i=0;i<=m;++i)
ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2lf\n",ans);
}