96pts

输入：

10 1 20 228
6 6 13 13 6 17 2 1 7 2
3 3 8 20 11 7 10 14 17 13
0.556 0.419 0.872 0.751 0.185 0.311 0.762 0.580 0.923 0.034
2 18 29
6 12 21
10 15 19
11 14 21
19 16 58
4 20 15
3 16 12
12 17 9
8 19 8
7 19 21
3 9 8
3 11 25
8 10 4
2 17 69
15 18 32
1 19 22
16 19 23
14 17 32
4 13 97
1 4 12
4 9 15
15 17 17
4 17 75
3 5 6
4 6 23
4 16 14
2 14 17
1 17 16
2 6 9
16 6 22
18 20 13
18 19 32
12 15 91
3 10 13
10 19 12
14 16 8
16 18 26
18 7 80
1 20 25
9 16 13
6 20 8
3 15 6
13 19 8
5 8 10
3 18 26
9 18 27
8 14 12
7 12 7
10 18 28
7 11 15
17 16 91
5 20 21
8 16 49
5 15 12
6 10 18
7 20 25
1 3 16
12 6 78
4 14 10
12 19 15
8 20 22
1 7 14
1 16 16
3 13 22
2 10 9
2 16 21
17 20 27
11 18 37
7 13 22
6 19 12
13 17 24
9 13 22
17 19 23
5 19 18
5 13 35
1 8 65
10 16 20
3 20 42
5 10 14
5 11 19
10 17 19
6 13 14
10 3 44
4 12 5
11 13 48
11 19 28
11 13 30
6 11 16
3 6 26
12 16 9
15 6 98
4 18 22
2 20 43
6 14 26
8 17 15
5 18 20
14 20 23
2 8 5
7 10 18
2 20 17
10 5 76
9 17 63
1 11 29
10 14 16
10 11 33
3 12 9
7 15 9
6 6 95
15 20 27
4 13 10
15 19 12
12 13 15
1 13 22
11 20 24
7 18 24
8 16 16
5 6 24
1 2 19
15 1 85
5 12 3
9 15 14
5 9 7
19 20 20
8 11 29
9 17 3
6 15 24
14 18 22
13 16 23
15 16 11
2 5 15
1 5 10
1 14 12
1 6 28
9 14 9
6 8 14
10 20 26
13 14 20
1 18 24
6 9 26
12 15 15
17 2 65
6 7 23
14 15 14
18 1 66
11 12 22
13 18 32
3 4 14
13 15 16
5 7 4
6 17 29
4 10 16
7 16 2
3 7 10
9 11 26
2 5 17
12 20 18
2 3 21
4 14 51
12 18 17
3 14 8
9 10 16
9 4 45
14 6 93
8 12 7
1 6 39
4 8 12
10 13 14
13 4 10
16 17 16
7 8 14
8 13 10
4 19 18
5 14 2
18 6 74
11 16 13
10 12 11
5 13 18
11 15 24
4 11 27
11 17 29
2 7 19
2 12 12
4 17 14
1 4 43
9 19 20
18 19 93
1 15 22
17 18 26
4 5 8
7 14 6
2 17 20
4 15 20
6 16 21
2 15 15
4 6 62
13 20 22
1 8 14
5 16 6
13 8 66
2 11 25
3 20 21
2 13 5
9 12 10
3 19 18
1 10 18
2 19 3
3 8 16
9 20 28
12 14 5
1 12 7
7 9 11
2 9 17
1 9 17
7 17 14
6 18 21
8 15 20
16 20 27
5 17 10
3 17 11
10 13 59
14 19 20
8 18 24
2 4 15
14 17 12
8 9 12
4 7 12
1 11 80
16 16 39

输出：

123.20

错误输出：

133.20

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3 + 7, MAXM = 3e2 + 7;

const int MAXE = 9e4 + 7, Inf = 1e9 + 7;

double F[MAXN][MAXN];

void add(int from, int to, double v) {
	F[from][to] = F[to][from] = min(F[from][to], v);
}

int n, m, v, e, C[MAXN], D[MAXN];

double k[MAXN];

void Floyd() {
	for (int k = 1; k <= v; k ++)
		for (int i = 1; i <= v; i ++)
			for (int j = 1; j <= v; j ++)
				F[i][j] = min(F[i][j], F[i][k] + F[k][j]);
}

double Ans[MAXN][MAXN][2];

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 >> k[i];
	
	for (int i = 1; i <= v; i ++)
			for (int j = 1; j <= v; j ++)
				F[i][j] = Inf;
	for (int i = 1, a, b, c; i <= e; i ++) 
		cin >> a >> b >> c, add(a, b, c);
	
	for (int i = 1; i <= n; i ++) F[i][i] = 0;
			
	Floyd();
	
	for (int i = 1; i <= n; i ++) for (int j = 0; j <= m; j ++) Ans[i][j][0] = Ans[i][j][1] = Inf;
	Ans[1][0][0] = Ans[1][1][1] = 0;

	for (int i = 2; i <= n; i ++) {
		for (int j = 0; j <= min(i, m); j ++) {
			int c1 = C[i - 1], d1 = D[i - 1], c2 = C[i], d2 = D[i];
			if (j) {
				Ans[i][j][1] = min({Ans[i-1][j-1][0] + k[i]*F[c1][d2] + (1 - k[i])*F[c1][c2],
								 Ans[i-1][j-1][1] + k[i-1]*k[i]*F[d1][d2] + 
								                    (1-k[i-1])*k[i]*F[c1][d2] +
													k[i-1]*(1-k[i])*F[d1][c2] +
													(1-k[i-1])*(1-k[i])*F[c1][c2], Ans[i][j][1]});
			}
			Ans[i][j][0] = min({Ans[i][j][0], Ans[i - 1][j][0] + F[c1][c2], 
											 Ans[i - 1][j][1] + k[i-1]*F[d1][c2] + 
											 					(1-k[i-1])*F[c1][c2]});
		}
	}
	
	double zans = Inf;
	for (int i = 0; i <= m; i ++) zans = min({zans, Ans[n][i][0], Ans[n][i][1]});
	printf("%.2f", zans);
	return 0;
}