对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 2n 2n 节课程安排在 n n 个时间段上。在第 i i （1≤i≤n 1 \leq i \leq n ）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 ci c_i 上课，而另一节课程在教室 di d_i 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 n n 节安排好的课程。如果学生想更换第i节课程的教室，则需要提出申请。若申请通过，学生就可以在第 i i 个时间段去教室 di d_i 上课，否则仍然在教室 ci c_i 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 i i 节课程的教室时，申请被通过的概率是一个已知的实数 ki k_i ，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 m m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请白己最希望更换教室的 m m 门课程，也可以不用完这 m m 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 v v 个教室，有 e e 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 i i （1≤i≤n−1 1 \leq i \leq n - 1 ）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

链接

LYOI#101

题解

这题说是考了期望，然而关于概率的内容只有期望的定义和概率的乘法计算，当然也考了十分冷门的 。

这道题只有 300 300 个教室，所以可以用 求出多源最短路，在用 的时候注意判断重边，而且要注意一个教室到它自己的距离为 0 0 ，即邻接矩阵中 g(i,i) \mathrm{g}(i,i) 应设为 0 0 而非常用的正无穷。

DP：

设状态 f(i,j,k) f(i,j,k) 表示在前 i i 个阶段，已经用掉了 j j 次申请机会，本次是否申请（k=0 k = 0 表示本次不申请，k=1 k = 1 表示本次申请）， 表示教室 i,ji, j 之间的距离。

考虑 f(i,j,0) f(i,j,0) 的转移，上一次可以申请，也可以不申请，反正本次一定不申请是确定的，则有：

f(i,j,0)=min{f(i−1,j,0)+dist(c(i−1),c(i))f(i−1,j,1)+dist(d(i−1),c(i))×k(i−1)+dist(c(i−1),c(i))×(1−k(i−1)) f(i, j, 0) = \min \begin{cases} f(i - 1, j, 0) + \mathrm{dist}(c(i - 1), c(i)) \\ \\ \begin{aligned} f(i - 1, j, 1) & + \mathrm{dist}(d(i - 1), c(i)) \times k(i - 1) \\ & + \mathrm{dist}(c(i - 1), c(i)) \times (1 - k(i - 1)) \end{aligned} \end{cases}

f(i,j,1) f(i,j,1) 的转移要长一点：

f(i,j,1)=min{f(i−1,j−1,0)+dist(c(i−1),d(i))×k(i)+dist(c(i−1),c(i))×(1−k(i))f(i−1,j−1,1)+dist(d(i−1),d(i))×k(i−1)×k(i)+dist(c(i−1),d(i))×(1−k(i−1))×k(i)+dist(d(i−1),c(i))×k(i−1)×(1−k(i))+dist(c(i−1),c(i))×(1−k(i−1))×(1−k(i)) f(i, j, 1) = \min \begin{cases} \begin{aligned} f(i - 1, j - 1, 0) &+ \mathrm{dist}(c(i - 1), d(i)) \times k(i) \\ &+ \mathrm{dist}(c(i - 1), c(i)) \times (1 - k(i)) \end{aligned} \\ \\ \begin{aligned} f(i - 1, j - 1, 1) &+ \mathrm{dist}(d(i - 1), d(i)) \times k(i - 1) \times k(i) \\ &+ \mathrm{dist}(c(i - 1), d(i)) \times (1 - k(i - 1)) \times k(i) \\ &+ \mathrm{dist}(d(i - 1), c(i)) \times k(i - 1) \times (1 - k(i)) \\ &+ \mathrm{dist}(c(i - 1), c(i)) \times (1 - k(i - 1)) \times (1 - k(i)) \end{aligned} \end{cases}

边界

f(i,0,1)=+∞f(1,0,0)=0 \begin{aligned} f(i, 0, 1) &= +\infty \\ f(1, 0, 0) &= 0 \end{aligned}

时间复杂度为 O(v3+nm) O(v ^ 3 + nm) 。

代码

#include <cstdio>
#include <cfloat>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 2000;
const int MAXM = 2000;
const int MAXV = 300;
const int MAXE = 90000;
int g[MAXV + 1][MAXV + 1], d[MAXN + 1], c[MAXN + 1], n, m, v, e;
double k[MAXN + 1];
void floyd () {
    for (int a = 1; a <= v; a++) {
        for (int b = 1; b <= v; b++) {
            for (int c = 1; c <= v; c++) {
                if (g[b][a] != INT_MAX && g[a][c] != INT_MAX && g[b][c] > g[b][a] + g[a][c]) {
                    g[b][c] = g[b][a] + g[a][c];
                }
            }
        }
    }
}
double f[MAXN + 1][MAXM + 1][2];
int main () {
    freopen("classroom.in", "r", stdin);
    freopen("classroom.out", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &v, &e);
    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 = 1; i <= v; i++) {
        for (int j = 1; j <= v; j++) {
            g[i][j] = INT_MAX;
        }
    }
    for (int i = 1; i <= e; i++) {
        int fr, to, w;
        scanf("%d %d %d", &fr, &to, &w);
        g[fr][to] = g[to][fr] = min(w, g[fr][to]);
    }
    floyd();
    for (int i = 1; i <= v; i++) g[i][i] = 0;
    f[1][0][0] = 0;
    f[1][0][1] = DBL_MAX;
    
    for (int i = 2; i <= n; i++) {
        f[i][0][0] = f[i - 1][0][0] + g[c[i - 1]][c[i]];
        f[i][0][1] = DBL_MAX;
        for (int j = 1; j <= m; j++) {
            f[i][j][0] = f[i][j][1] = DBL_MAX;
            if (f[i - 1][j][0] != DBL_MAX) {
                f[i][j][0] = min(f[i][j][0], f[i - 1][j][0] 
                         + g[c[i - 1]][c[i]]);
            }
            if (f[i - 1][j][1] != DBL_MAX) {
                f[i][j][0] = min(f[i][j][0], f[i - 1][j][1] 
                         + (g[c[i - 1]][c[i]] * (1 - k[i - 1]))
                         + (g[d[i - 1]][c[i]] * k[i - 1]));
            }
            if (f[i - 1][j - 1][0] != DBL_MAX) {
                f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][0] 
                        + (g[c[i - 1]][d[i]] * k[i]) 
                        + (g[c[i - 1]][c[i]] * (1 - k[i])));
            }
            if (f[i - 1][j - 1][1] != DBL_MAX) {
                f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][1]
                        + (g[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]))
                        + (g[d[i - 1]][c[i]] * k[i - 1] * (1 - k[i]))
                        + (g[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i])
                        + (g[d[i - 1]][d[i]] * k[i - 1] * k[i]));
            }
        }
    }
    
    double ans = DBL_MAX;
    for (int j = 0; j <= m; j++) {
        ans = min(ans, f[n][j][0]);
        ans = min(ans, f[n][j][1]);
    }
    printf("%.2lf\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}