题解

#include <bits/stdc++.h>
using namespace std;
#define lson(u) (u<<1)
#define rson(u) (u<<1|1)
#define Pi acos(-1)
#define iINF 0x3f3f3f3f
#define lINF 0x3f3f3f3f3f3f3f
#define EPS 0.000000001
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int MAXN1=2005;
const int MAXN2=305;
const ll Mod=1e9+7;
int n,m,v,e;
int C[MAXN1],D[MAXN1];
double K[MAXN1],f[MAXN1][MAXN1][2],dis[MAXN2][MAXN2]; 
void floyd()
{
	for(int k=1;k<=v;k++)
	{
		for(int i=1;i<=v;i++)
		{
			for(int j=1;j<=v;j++)
			{
				if(dis[i][j]>dis[i][k]+dis[k][j])
				{
					dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}
}
void Init()
{
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			dis[i][j]=iINF;
		}
	}
	for(int i=1;i<=v;i++)
	{
		dis[i][i] = 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			f[i][j][0]=f[i][j][1]=iINF;
		}
	}
}
int main()
{
	int x,y,xy;
	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",&K[i]);
	}
	Init();
	for(int i=0;i<e;i++) 
	{
		scanf("%d%d%d",&x,&y,&xy);
		dis[x][y]=min(dis[x][y],double(xy));
		dis[y][x]=min(dis[y][x],double(xy));
	}
	floyd();
	double dis1,dis2; 
	double ans=iINF; 
	f[1][0][0]=f[1][1][1]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=m&&j<=i;j++)
		{
			dis1=dis[C[i]][C[i-1]];
			dis2=dis[C[i]][D[i-1]]*K[i-1] + dis[C[i]][C[i-1]]*(1.0-K[i-1]);
			if(j==0)
			{
				f[i][j][0]=f[i-1][j][0]+dis1;
			}
			else
			{
				f[i][j][0] = min(f[i-1][j][0] + dis1, f[i-1][j][1] + dis2);
			}
			if(j == 0)
			{
				continue;
			}
			dis1=dis[D[i]][C[i-1]]*K[i]+dis[C[i]][C[i-1]]*(1.0-K[i]);
			dis2=dis[D[i]][D[i-1]]*K[i]*K[i-1]+dis[D[i]][C[i-1]]*K[i]*(1.0-K[i-1])+dis[C[i]][D[i-1]]*(1.0-K[i])*K[i-1]+dis[C[i]][C[i-1]]*(1.0-K[i])*(1.0-K[i-1]);
			f[i][j][1]=min(f[i-1][j-1][0]+dis1,f[i-1][j-1][1]+dis2);
		}
	}
	for(int j=0;j<=m&&j<=n;j++) {
		ans=min(ans,f[n][j][0]);
		ans=min(ans,f[n][j][1]);
	}
	printf("%0.2lf",ans);
	return 0;
}