一道很有意思的概率dp题。
一开始我是想求出到达$c_i/d_i$教室的期望值，后面发现这样做有bug。
又读了一遍题目，发现我们要求如何提交申请使得期望值最小，所以在dp的时候必须要以是提交申请为状态
于是我分类讨论了一下状态转移（假设n只有2）：
注：上面的点表示成功，下面的点表示失败，b表示概率

情况一，1换，2不换

情况二，1换，2换

情况三，1不换，2换

情况四，1不换，2不换

然后就可以dp了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, M = 3e2 + 10;
int n, m, V, E, c[N], d[N], a[M][M];
double b[N], f[2][N][2]; 
void init(int p) {for (int i = 0; i <= m; i++) f[p][i][0] = f[p][i][1] = 1000000000.0;}
int 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 >> b[i];
    memset(a, 0x3f, sizeof(a));
    for (int i = 1; i <= V; i++) a[i][i] = 0;
    for (int i = 1; i <= E; i++) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        if (z < a[x][y]) a[x][y] = a[y][x] = z;
    }
    for (int k = 1; k <= V; k++)
        for (int i = 1; i <= V; i++)
            for (int j = 1; j <= V; j++)
                if (a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
    init(0); f[0][0][0] = f[0][1][1] = 0.0;
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p ^= 1; init(p);
        for (int j = 0; j <= m; j++) {
            f[p][j][0] = f[p ^ 1][j][0] + 1.0 * a[c[i - 1]][c[i]];
            if (j) f[p][j][0] = min(f[p][j][0], f[p ^ 1][j][1] + 1.0 * b[i - 1] * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * a[c[i - 1]][c[i]]);
            if (!j) continue;
            f[p][j][1] = f[p ^ 1][j - 1][0] + 1.0 * b[i] * a[c[i - 1]][d[i]] + 1.0 * (1.0 - b[i]) * a[c[i - 1]][c[i]];
            if (j > 1) f[p][j][1] = min(f[p][j][1], f[p ^ 1][j - 1][1] + 1.0 * b[i - 1] * (1.0 - b[i]) * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * (1.0 - b[i]) * a[c[i - 1]][c[i]] + 1.0 * b[i - 1] * b[i] * a[d[i - 1]][d[i]] +1.0 * (1.0 - b[i - 1]) * b[i] * a[c[i - 1]][d[i]]);
        }
    }
    double ans = 100000000.0;
    for (int i = 0; i <= m; i++) ans = min(ans, min(f[p][i][0], f[p][i][1]));
    printf("%.2lf\n", ans);
    return 0;
}