前言
被绕进去了，瞄了一眼题解，发现状态有点问题。
当然转移还是可以自己写的。
题目
讲解
首先这道题很容易陷入这样一个误区：我dp要转移，必须要知道前一个位置在哪里，那么顺理成章地，定义状态 \(dp_{i,j,0/1}\) 表示第 \(i\) 个课程，申请了 \(j\) 次，现在在 \(0/1\) 位置的最小期望路程。
但是这样新的问题就出现了，你的上一步是哪一个位置呢？或者说你用什么来更新当前状态呢？用最小值？但是你不知道你上一步到底有没有申请成功(申请是一次性全部提交)，而且我甚至无法判断当前状态是否应该申请换教室。
所以我们换个思路，申请是独立的，那么用申请来当状态就没有后效性了！
令 \(dp_{i,j,0/1}\) 表示第 \(i\) 个课程，申请了 \(j\) 次，现在在是否申请换教室的最小期望路程，这样一来转移就简单多了。
当然 \(\tt Floyd\) 预处理最短路就不用多说了吧。
时间复杂度 \(O(nm+V^3)\)。
代码
具体转移可以看代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 2005;
const int INF = 0x3f3f3f3f;
int n,m,V,E;
int c[MAXN],d[MAXN];
double p[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int e[MAXN][MAXN];
double dp[MAXN][MAXN][2];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
memset(e,0x3f,sizeof(e));
n = Read(); m = Read(); V = Read(); E = Read();
for(int i = 1;i <= V;++ i) e[i][i] = 0;
for(int i = 1;i <= n;++ i) c[i] = Read();
for(int i = 1;i <= n;++ i) d[i] = Read();
for(int i = 1;i <= n;++ i) scanf("%lf",&p[i]);
for(int i = 1;i <= E;++ i)
{
int u = Read(),v = Read();
e[u][v] = Min(0ll+e[u][v],Read());
e[v][u] = e[u][v];
}
for(int k = 1;k <= V;++ k)
for(int i = 1;i <= V;++ i)
for(int j = 1;j <= V;++ j)
e[i][j] = Min(e[i][j],e[i][k]+e[k][j]);
for(int i = 1;i <= n;++ i)
for(int j = 0;j <= m;++ j)
dp[i][j][0] = dp[i][j][1] = INF;
dp[1][0][0] = dp[1][1][1] = dp[1][1][0] = 0;
for(int i = 2;i <= n;++ i)
for(int j = 0;j <= m;++ j)
{
dp[i][j][0] = Min(dp[i-1][j][0]+e[c[i-1]][c[i]],dp[i-1][j][1]+p[i-1]*e[d[i-1]][c[i]]+(1-p[i-1])*e[c[i-1]][c[i]]);
if(j)
{
dp[i][j][1] = dp[i-1][j-1][0]+p[i]*e[c[i-1]][d[i]]+(1-p[i])*e[c[i-1]][c[i]];
double val = 0;
for(int k = 0;k < 2;++ k)
for(int l = 0;l < 2;++ l)
{
double fk = 1;
int u,v;
if(!k) fk *= 1-p[i-1],u = c[i-1];
else fk *= p[i-1],u = d[i-1];
if(!l) fk *= 1-p[i],v = c[i];
else fk *= p[i],v = d[i];
val += fk * e[u][v];
}
dp[i][j][1] = Min(dp[i][j][1],dp[i-1][j-1][1]+val);
}
}
double ans = INF;
for(int i = 0;i <= m;++ i) ans = Min(ans,Min(dp[n][i][0],dp[n][i][1]));
printf("%.2f\n",ans);
return 0;
}