以下是我的代码。C语言，DP，倒推，在洛谷的评测中WA了16，17，18这三个点。

$dist[i, j]$ 代表两个教室之间的距离（由Floyd算法求出）， $f[i, j]$ 代表在第 $i$ 天时如果在 $c[i]$ 教室，并且有 $j$ 次更换机会，从这一天开始到最后一天的最小期望； $g[i, j]$ 类似，第 $i$ 天从 $d[i]$ 开始。

#include <stdio.h>
#include <string.h>

int n, m, v, e;

int tab[301][301], dist[301][301];
int c[2001], d[2001];
double k[2001];
double f[2001][2001], g[2001][2001];

int main(void) {
    memset(tab, 0x3f, sizeof(tab));
    scanf("%d%d%d%d", &n, &m, &v, &e);
    for (int i = 1; i <= v; i++) {
        tab[i][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", c + i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", d + i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lf", k + i);
    }
    for (int i = 0; i < e; i++) {
        int x, y, w; scanf("%d%d%d", &x, &y, &w);
        if (w < tab[x][y]) {
            tab[x][y] = tab[y][x] = w;
        }
    }
    tab[c[0]][c[1]] = tab[c[0]][d[1]] = tab[d[0]][c[1]] = tab[d[0]][d[1]] = 0;
    memcpy(dist, tab, sizeof(dist));
    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    for (int j = 0; j <= m; j++) {
        f[n][j] = g[n][j] = 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        f[i][0] = dist[c[i]][c[i + 1]] + f[i + 1][0];
        g[i][0] = dist[d[i]][c[i + 1]] + f[i + 1][0];
        for (int j = 1; j <= m; j++) {
            f[i][j] = dist[c[i]][c[i + 1]] + f[i + 1][j];
            g[i][j] = dist[d[i]][c[i + 1]] + f[i + 1][j];
            double tmp = k[i + 1] * (dist[c[i]][d[i + 1]] + g[i + 1][j - 1])
                + (1.0 - k[i + 1]) * (dist[c[i]][c[i + 1]] + f[i + 1][j - 1]);
            if (tmp < f[i][j]) {
                f[i][j] = tmp;
            }
            tmp = k[i + 1] * (dist[d[i]][d[i + 1]] + g[i + 1][j - 1])
                + (1.0 - k[i + 1]) * (dist[d[i]][c[i + 1]] + f[i + 1][j - 1]);
            if (tmp < g[i][j]) {
                g[i][j] = tmp;
            }
        }
    }
    printf("%.2lf\n", f[0][m] < g[0][m] ? f[0][m] : g[0][m]);
}