题解

思路分析

题目求在提前申请最多 m 节课调换教室的前提下，Bessie 在全部课程之间移动的最小期望距离。核心拆解为：

1. 最短路预处理：教室个数 v ≤ 300，直接使用 Floyd–Warshall 算法得到任意两教室的最短距离 G[x][y]。
2. 动态规划计算期望：设 E[i][j][k] 表示到达第 i 节课时，已经提交了 j 次申请，并且第 i 节课最终在原教室 (k = 0) 或备选教室 (k = 1) 上课时的最小期望移动距离。转移时：
   • 不申请或申请失败：继承上一节的状态并加上对应最短路距离；
   • 申请且成功：根据前一节是否申请成功、当前节是否成功产生四种概率，加权累加距离。

枚举 j 取 min(E[n][j][0], E[n][j][1]) 即可得到答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
const int M = 310;

int G[M][M], n, m, v, e;
int c[N], d[N];
double E[N][N][2], p[N];

int main() {
	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", &p[i]);
	}
	memset(G, 0x3f, sizeof G);
	for (int i = 1; i <= e; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u][v] = min(G[u][v], w);
		G[v][u] = min(G[v][u], w);
	}
	for (int i = 1; i <= v; i++) {
		G[i][i] = G[i][0] = G[0][i] = 0;
	}
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			E[i][j][0] = E[i][j][1] = 1e9;
		}
	}
	E[1][0][0] = E[1][1][1] = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= min(i, m); j++) {
			if (j == 0) {
				E[i][j][0] = E[i-1][j][0]+G[c[i-1]][c[i]];
			} else {
				E[i][j][0] = min(E[i][j][0], E[i-1][j][0]+G[c[i-1]][c[i]]);
				E[i][j][0] = min(E[i][j][0], E[i-1][j][1]+p[i-1]*G[d[i-1]][c[i]]+(1.0-p[i-1])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][0]+p[i]*G[c[i-1]][d[i]]+(1-p[i])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][1]+p[i-1]*p[i]*G[d[i-1]][d[i]]+p[i-1]*(1-p[i])*G[d[i-1]][c[i]]+(1-p[i-1])*p[i]*G[c[i-1]][d[i]]+(1-p[i-1])*(1-p[i])*G[c[i-1]][c[i]]);
			}
//			printf("(%.2lf, %.2lf) ", E[i][j][0], E[i][j][1]);
		}
//		printf("\n");
	}
	double rst = 1e9;
	for (int i = 0; i <= m; i++) {
		rst = min(rst, min(E[n][i][0], E[n][i][1]));
	}
	printf("%.2lf", rst);
	
	return 0;
}