跟大多数题解不一样，我采用的是逆推法，即$f[i][j][pos]$表示从$i$出发，换$j$次课的最小期望，$pos$为0表示当前在$c[i]$上，为1表示在$d[i]$。

然而只有88分，查不出哪里错了。

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 2e3 + 10, MAXV = 300 + 10;
const int INF = 1e9;

int n, m, v, e, c[MAXN][2];
double p[MAXN], f[MAXN][MAXN][2];

int d[MAXV][MAXV];

double solve()
{
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			f[i][j][0] = f[i][j][1] = INF;
	f[n][0][0] = f[n][0][1] = 0;
	
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j <= m; j++)
			for (int pos = 0; pos < 2; pos++)
			{
				int C = c[i][pos], C2 = c[i + 1][0], D2 = c[i + 1][1];
				f[i][j][pos] = min(f[i][j][pos], f[i + 1][j][0] + d[C][C2]);
				if (j)
				{
					double E = 0;
					E += p[i + 1] * (f[i + 1][j - 1][1] + d[C][D2]);
					E += (1 - p[i + 1]) * (f[i + 1][j - 1][0] + d[C][C2]);
					f[i][j][pos] = min(f[i][j][pos], E);
				}
//				printf("f[%d][%d][%d] = %.2lf\n", i, j, pos, f[i][j][pos]);
			}
		
	double ans = INF;
	for (int j = 0; j <= m; j++)
		ans = min(ans, f[0][j][0]);
	return ans;
}

int main()
{
//	freopen("input.txt", "r", stdin);
	cin >> n >> m >> v >> e;
	for (int i = 1; i <= n; i++)
		scanf("%d", &c[i][0]);
	for (int i = 1; i <= n; i++)
		scanf("%d", &c[i][1]);
	for (int i = 1; i <= n; i++)
		scanf("%lf", &p[i]); 
	
	memset(d, 0x3f, sizeof(d));
	for (int i = 0; i <= v; i++)
		d[i][i] = d[0][i] = d[i][0] = 0;
	int a, b, w;
	for (int i = 1; i <= e; i++)
	{
		scanf("%d %d %d", &a, &b, &w);
		d[a][b] = min(d[a][b], w);
		d[b][a] = min(d[b][a], w);
	}
	
	for (int k = 1; k <= v; k++)
		for (int i = 1; i <= v; i++)
			for (int j = 1; j <= v; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	printf("%.2lf\n", solve());
}