不用看转移,转移我和题解对了的,帮我看看细节有没有写错,如初始化
#include<bits/stdc++.h>
using namespace std;
int n,m,v,e;
int c[2010],d[2010];
double k[2010];
int f[310][310]; //floyd
double dp[2010][2010][2],ans=1e9;
double min(double a,double b){
if(a<=b)return a;
else return b;
}
int main(){
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]=1e9;
for(int i=1;i<=e;i++){
int U,V,W;
cin>>U>>V>>W;
f[U][V]=W;
f[V][U]=W;
}
for(int k=1;k<=v;k++)
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][i]);
for(int i=1;i<=v;i++)
f[i][i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j][1]=dp[i][j][0]=1e9;
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=n;i++){
dp[i][0][0]=dp[i-1][0][0]+f[c[i-1]][c[i]];
for(int j=1;j<=m;j++){
dp[i][j][0]=min(
dp[i-1][j][0]+f[c[i-1]][c[i]], //i-1不变
dp[i-1][j][1]+f[d[i-1]][c[i]]*k[i-1]+f[c[i-1]][c[i]]*(1-k[i-1])); //i-1变
//i不变
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]), //i-1不变
dp[i-1][j-1][1]+f[d[i-1]][d[i]]*k[i]*k[i-1]+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])//i-1变
);
}
}
for(int i=0;i<=m;i++)
ans=min(ans,min(dp[n][i][1],dp[n][i][0]));
printf("%.2lf",ans);
return 0;
}