期望DP
因为
课程是按时间顺序的，后面的变化不会影响前面的结果
对于每个时间段的课，只有两种选择（换 or 不换）
那么
显然 $DP$，而且 好像 转移也很好写...
显然设 $dp [ i ] [ j ]$ 表示到了第 i 个时间段，已经提交了 j 节课的申请时的最短期望路程
写到一半发现
好像转不了...
因为不知道当前是在哪个教室，自然不知道期望路程是多少...
好像凉了..
没事，多开一维 $k$ ，$k=0$ 表示第 $i$ 个时间段不提交申请，$k=1$ 表示提交申请
这样就知道在 $c[ i ]$ 和 $d[ i ]$ 教室上课的概率(注意是概率，因为有可能申请失败)，然后就可以知道期望路程了
设 $f[ i ]$ 为申请第 $i$ 节课通过的概率，$dis[ i ][ j ]$ 为从教室 $i$ 到教室 $j$ 的最短路程
所以 $dp [ i ] [ j ] [ 0 ] = min（dp[ i-1][ j ][ 0 ]+dis[ c[ i-1 ] ][ c[ i ] ]*1.0*1.0$，
$dp[i-1][j][1]+(dis[d[i-1]][c[i]]*f[i-1]*1.0)+$
$(dis[c[i-1]][c[i]])*(1-f[i-1]*1.0))$
$dis$ 乘上的第一个数表示上一次的概率，第二个数表示这一次的概率
因为我们还不知道上一次是否申请成功，所以如果有申请就要考虑成功和失败的情况
所以期望路程就是 路程*走这条路的概率
如果没申请就肯定失败，所以期望路程就是 申请失败的路程*100%
对于 $dp[ i ] [ j ] [1]$ 也是用类似的方法转移，但是要注意这一次也有失败的可能
所以转移会比较麻烦一些：
$dp[ i ] [ j ] [ 1 ] = min（dp[ i-1][ j-1][ 0 ] + dis[ c[ i-1] ][ d[ i ] ]*1.0*f[ i ] + dis[ c[i-1] ][ c[ i ] ]*1.0*(1.0-f[ i ])$，
$dp[ i-1][ j-1][1] + dis[ d[ i-1 ] ][ d[ i ] ]*f[ i-1]*f[ i ] +$
$dis[d[i-1]][c[i]]*f[i-1]*(1.0-f[i])+$
$dis[ c[ i-1] ][ d[ i ] ]*(1.0-f[ i-1 ])*f[ i ] +$
$dis[ c[ i-1] ][ c[ i ] ]*(1.0-f[ i-1])*(1.0-f[ i ])$ ）
转移好像没这么简单....
好了有了转移就一点难度都没有了
预处理两点间的最短路径就用 $floyd$ 就好了
（写这题的时候改了半天，结果是 $floyd$ 错了...）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; const int N=2007; int n,m,t,e; int c[30007],d[20007]; double dp[N][N][2],f[10007],dis[N][N]; int main() { cin>>n>>m>>t>>e; for(int i=1;i<=t;i++) for(int j=1;j<i;j++) dis[i][j]=dis[j][i]=99999999.0; 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",&f[i]); int a,b; double g; for(int i=1;i<=e;i++) { scanf("%d%d%lf",&a,&b,&g); dis[a][b]=dis[b][a]=min(dis[a][b],g); } for(int k=1;k<=t;k++) for(int i=1;i<=t;i++) for(int j=1;j<i;j++) if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j]; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j][0]=dp[i][j][1]=99999999.0; dp[1][0][0]=dp[1][1][1]=0.0; for(int i=2;i<=n;i++) for(int j=0;j<=m;j++) { dp[i][j][0]=min( dp[i-1][j][0]+dis[c[i-1]][c[i]]*1.0*1.0 , dp[i-1][j][1] + dis[d[i-1]][c[i]]*f[i-1]*1.0 + dis[c[i-1]][c[i]]*(1-f[i-1])*1.0 ); if(j>0) dp[i][j][1]=min( dp[i-1][j-1][0]+dis[c[i-1]][d[i]]*1.0*f[i] + dis[c[i-1]][c[i]]*1.0*(1.0-f[i]) , dp[i-1][j-1][1]+dis[d[i-1]][d[i]]*f[i-1]*f[i] + dis[d[i-1]][c[i]]*f[i-1]*(1.0-f[i]) + dis[c[i-1]][d[i]]*(1.0-f[i-1])*f[i] + dis[c[i-1]][c[i]]*(1.0-f[i-1])*(1.0-f[i]) ); } double ans=99999999.0; for(int i=0;i<=m;i++) ans=min(ans, min(dp[n][i][0],dp[n][i][1]) ); printf("%.2lf",ans); return 0; }