简要的证明一下floyd算法的正确性.想必大家都做过旅行商问题(状态压缩).floyd就是暴力枚举了每个点的对整幅图的贡献.
然后就是讲下这个题,这个题是个概率dp,因为要求最小.首先得明确dp所表示的含义.我们令f[i][j][0/1]表示我们学到了第i门课,我们用了j次机会,第j次的时候用了/没用的期望最短距离.转移方程就比较容易了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N=2e3+5;
const int M=3e2+5;
int a[N],b[N];
int dis[M][M];
double f[N][N][2];
double p[N];
int main()
{
    int n,m,e,v;
    cin>>n>>m>>v>>e;
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)   scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)   scanf("%lf",&p[i]);
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=v;i++)   dis[i][i]=0;
    while(e--)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=min(w, dis[x][y]);
        dis[y][x]=min(w, dis[y][x]);
    }
    for(int k=1;k<=v;k++)
    {
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<2;k++)
            {
                f[i][j][k]=2e9;           
            }
        }
    }    
    f[1][0][0]=0,0;f[1][1][1]=0.0;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j][0]=min(f[i-1][j][0]+dis[a[i-1]][a[i]],f[i-1][j][1]+dis[a[i-1]][a[i]]*(1-p[i-1])+dis[b[i-1]][a[i]]*(p[i-1]));
            if(j)
            {
                f[i][j][1]=min(f[i-1][j-1][0]+(1-p[i])*dis[a[i-1]][a[i]]+(p[i])*dis[a[i-1]][b[i]],f[i-1][j-1][1]+
                dis[a[i-1]][a[i]]*(1-p[i])*(1-p[i-1])+
                dis[a[i-1]][b[i]]*(p[i])*(1-p[i-1])+
                dis[b[i-1]][a[i]]*(1-p[i])*(p[i-1])+
                dis[b[i-1]][b[i]]*(p[i])*(p[i-1])
                );
            }
        }
    }
    double ans=2e9;
    for(int i=0;i<=m;i++)  ans=min(ans,min(f[n][i][0],f[n][i][1]));
    printf("%.2lf\n",ans);
    return 0;
}