WA on #25

#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=2005;
int dis[N][N];
double dp[N][N][2],p[N];
int a[N],b[N];
int n,m,v,e;
signed main(){
	n=read(),m=read(),v=read(),e=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			dis[i][j]=1e15;
		}
	}
	for(int i=0;i<=n;i++) dis[i][i]=dis[i][0]=dis[0][i]=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i][j][0]=dp[i][j][1]=1e15;
		}
	}
	for(int i=1;i<=e;i++){
		int x=read(),y=read(),d=read();
		dis[x][y]=dis[y][x]=min(dis[x][y],d);
	}
	for(int k=1;k<=v;k++){
		for(int i=1;i<=v;i++){
			for(int j=1;j<=v;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	dp[1][0][0]=dp[1][1][1]=0.0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0]+dis[a[i-1]][a[i]];
		for(int j=1;j<=min(i,m);j++){
			dp[i][j][0]=min(dp[i-1][j][0]+dis[a[i-1]][a[i]],dp[i-1][j][1]+dis[a[i-1]][a[i]]*(1.0-p[i-1])+dis[b[i-1]][a[i]]*p[i-1]);
			dp[i][j][1]=min(dp[i-1][j-1][0]+dis[a[i-1]][b[i]]*p[i]+dis[a[i-1]][a[i]]*(1.0-p[i]),dp[i-1][j-1][1]+dis[b[i-1]][b[i]]*p[i]*p[i-1]+dis[b[i-1]][a[i]]*(1.0-p[i])*p[i-1]+dis[a[i-1]][b[i]]*(1.0-p[i-1])*p[i]+dis[a[i-1]][a[i]]*(1.0-p[i-1])*(1.0-p[i]));
		}
	}
	double ans=1e15;
	for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
	printf("%.2lf\n",ans);
	return 0;
}