#include<bits/stdc++.h>
using namespace std;
const int N=2005,T=305;
int n,m,t,e,c[N],d[N],f[T][T];
double k[N],dp[2][N][2];

int main()
{
//	freopen("P1850_16.in","r",stdin);
	memset(f,0x3f,sizeof(f));
	scanf("%d%d%d%d",&n,&m,&t,&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]);
	for(int i=1,x,y,z;i<=e;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		f[x][y]=f[y][x]=min(f[x][y],z);
	}
	for(int i=1;i<=t;i++) f[i][i]=0;
	for(int l=1;l<=t;l++)
		for(int i=1;i<=t;i++)
			for(int j=1;j<=t;j++)
				f[i][j]=min(f[i][j],f[i][l]+f[l][j]);	
	dp[1][0][0]=0,dp[1][1][1]=0,dp[1][0][1]=dp[0][0][1]=1e10;
	for(int i=2;i<=n;i++) 
	{
		for(int j=0;j<=min(i,m);j++) 
		{
			dp[i&1][j][0]=min(dp[i-1&1][j][0]+f[c[i-1]][c[i]],dp[i-1&1][j][1]+f[d[i-1]][c[i]]*k[i-1]+f[c[i-1]][c[i]]*(1-k[i-1]));
			dp[i&1][j+1][1]=min(dp[i-1&1][j][0]+f[c[i-1]][d[i]]*k[i]+f[c[i-1]][c[i]]*(1-k[i]),dp[i-1&1][j][1]+f[d[i-1]][d[i]]*k[i-1]*k[i]+f[d[i-1]][c[i]]*k[i-1]*(1-k[i])+f[c[i-1]][d[i]]*(1-k[i-1])*k[i]+f[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i]));
		}
	}
	double ans=dp[n&1][0][0];
	for(int i=1;i<=m;i++) ans=min(ans,min(dp[n&1][i][0],dp[n&1][i][1]));
	printf("%.2lf\n",ans);
	return 0;
} 

DP[i,j,0/1]表示前 i 个有 j 个申请当前第 i 个是否取的最小期望值。

代码清晰易懂，望大佬帮忙调一下