分析来自

#include<bits/stdc++.h>
#define N 2005
using namespace std;
int n,m,v,e;
int c[N],d[N];
double k[N];
int s,t,w;
int rood[305][305];
double dp[N][N][3],ans=999999999;
int main()
{
    memset(rood,10,sizeof(rood));
    for(int i=0;i<=300;i++) rood[i][i]=0;
    for(int i=0;i<=2000;i++) for(int j=0;j<=4000;j++) dp[i][j][0]=dp[i][j][1]=ans;
    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<=e;i++){
        cin>>s>>t>>w;
        rood[s][t]=min(rood[s][t],w);
        rood[t][s]=min(rood[t][s],w);
    }
    for(int z=1;z<=v;z++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                rood[i][j]=min(rood[i][j],rood[i][z]+rood[z][j]);
    dp[1][m][0]=0;
    if(m) dp[1][m-1][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j][0]=min(dp[i][j][0], dp[i-1][j][0]   + rood[c[i-1]][c[i]] );
            dp[i][j][0]=min(dp[i][j][0], dp[i-1][j][1]   + k[i-1]*rood[d[i-1]][c[i]]      + (1.0-k[i-1])*rood[c[i-1]][c[i]] );
            dp[i][j][1]=min(dp[i][j][1], dp[i-1][j+1][0] + k[i]*rood[c[i-1]][d[i]]        + (1.0-k[i])*rood[c[i-1]][c[i]]   );
            dp[i][j][1]=min(dp[i][j][1], dp[i-1][j+1][1] + k[i-1]*k[i]*rood[d[i-1]][d[i]] + (1.0-k[i-1])*k[i]*rood[c[i-1]][d[i]] + k[i-1]*(1.0-k[i])*rood[d[i-1]][c[i]] +(1.0-k[i-1])*(1.0-k[i])*rood[c[i-1]][c[i]] );
        }
    }
    for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2f\n",ans);
    return 0;
}