这个题细节太多了，重点是当初做时第一遍蒙蔽 第二遍看题解看傻了、所以再写还是有问题
1、一遍一定尽量把代码打对、
2、循环变量名、、
3、时刻保持紧张、
期望dp：概率*权值，利用可加性，无后效性（每个事件的概率不变），直接o(n)推出、
码
#include<iostream> #include<cstdio> using namespace std; #include<cstring> #define N 2005 int n,m,v,e,i,j,k,x,y,a[2005],b[2005],f[305][305],z; double gailv[2005],g[2005][2005][2]; int main() { scanf("%d%d%d%d",&n,&m,&v,&e); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(j=1;j<=n;j++)scanf("%d",&b[j]); for(i=1;i<=n;i++)scanf("%lf",&gailv[i]); memset(f,60,sizeof(f)); for(i=1;i<=v;i++)f[i][i]=0; for(i=1;i<=e;i++) { scanf("%d%d%d",&x,&y,&z); f[x][y]=f[y][x]=min(f[x][y],z); } for(k=1;k<=v;k++) for(i=1;i<=v;i++) for(j=1;j<=v;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); memset(g,127,sizeof(g)); g[1][0][0]=0; g[1][1][1]=0; for(i=1;i<n;i++) for(j=0;j<=min(i,m);j++) { if(g[i][j][0]<1e20) {//cout<<"p"<<endl; g[i+1][j][0]=min(g[i+1][j][0],g[i][j][0]+f[a[i]][a[i+1]]); if(j<m)g[i+1][j+1][1]=min(g[i+1][j+1][1],g[i][j][0]+f[a[i]][b[i+1]]*gailv[i+1]+(1-gailv[i+1])*f[a[i]][a[i+1]]); } if(g[i][j][1]<1e20) { g[i+1][j][0]=min(g[i+1][j][0],g[i][j][1]+gailv[i]*f[b[i]][a[i+1]]+(1-gailv[i])*f[a[i]][a[i+1]]); if(j<m)g[i+1][j+1][1]=min(g[i+1][j+1][1],g[i][j][1]+gailv[i]*gailv[i+1]*f[b[i]][b[i+1]]+(1-gailv[i])*gailv[i+1]*f[a[i]][b[i+1]]+gailv[i]*(1-gailv[i+1])*f[b[i]][a[i+1]]+(1-gailv[i])*(1-gailv[i+1])*f[a[i]][a[i+1]]); } } double ans=1e20; for(int i=m;i>=0;--i)ans=min(ans,min(g[n][i][0],g[n][i][1])); printf("%.2f\n",ans); }