记录编号	610884	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.834 s
提交时间	2026-01-24 09:25:45	内存使用	12.80 MiB

#include<iostream>
#include<algorithm>
#include<iomanip>
//#define int long long
using namespace std;

const int MAXN = 2005;
const int MAXV = 305;
double f[MAXV][MAXV];
int n,m,e,v;
int c[MAXN],d[MAXN];
double k[MAXN];
double dp[MAXN][MAXN][2];

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	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] = 1e18;
		}
		f[i][i] = 0;
	}
	for(int u,v,w,i = 1;i <= e;i ++){
		cin >> u >> v >> w;
		f[v][u] = f[u][v] = min(f[u][v],w * 1.0);
	}
	for(int t = 1;t <= v;t ++){
		for(int i = 1;i <= v;i ++){
			for(int j = 1;j <= v;j ++){
				if(f[i][t] + f[t][j] < f[i][j]){
					f[i][j] = f[i][t] + f[t][j];
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][1] = dp[i][j][0] = 1e18;
		}
	}
	dp[1][0][0] = 0;
	dp[1][1][1] = 0;
	for(int i = 2;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],dp[i - 1][j][1] + k[i - 1] * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * f[c[i - 1]][c[i]]);
			if(j > 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * k[i] + f[c[i - 1]][c[i]] * (1 - k[i]),dp[i - 1][j - 1][1] + k[i - 1] * k[i] * f[d[i - 1]][d[i]] + k[i - 1] * (1 - k[i]) * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * k[i] * f[c[i - 1]][d[i]] + (1 - k[i - 1]) * (1 - k[i]) * f[c[i - 1]][c[i]]);
		}
	}
	double ans = 1e18;
	for(int i = 0;i <= m;i ++){
		ans = min(ans,min(dp[n][i][1],dp[n][i][0]));
	}
	cout << fixed << setprecision(2) << ans << '\n';
	return 0;
}