題目：https://www.luogu.com.cn/problem/P1850

思路：

概率dp,如果要求最小路徑期望，我們要確定的有選了幾節課，申請換了幾節課，最后一節是否申請換課（下一次選課要知道上一次選課申請情況）。

設f[k][i][j](k=0||k=1);k=0表示當前這節課不申請換教室，k=1申請換教室。

dis[i][j]從i到j距離；（用flord求任意兩點最短距離）；

c[i],d[i],k[i]和題意里相同含義；

如果當前這節課不申請，f[0][i][j]取值情況：

1.上節課申請：f[1][i-1][j]+k[i-1]*dis[c[i]][d[i-1]]+1.0*(1-k[i-1])*dis[c[i]][c[i-1]];

2.上節課不申請：f[0][i-1][j]+dis[c[i]][c[i-1]]；

如果上節課不申請，第i個點到i-1點距離為dis[c[i]][c[i-1]]，申請，可能路徑有兩條，dis[c[i]][d[i-1]]，dis[c[i]][c[i-1]]，求的是期望，所以相應的距離乘上相應概率；

如果這節課申請，f[1][i][j]取值情況：

1.上節課申請：f[1][i-1][j-1]+1.0*dis[c[i]][c[i-1]]*(1-k[i])*(1-k[i-1])+1.0*dis[c[i]][d[i-1]]*(1-k[i])*k[i-1]
?? ?+1.0*dis[d[i]][c[i-1]]*k[i]*(1-k[i-1])+1.0*dis[d[i]][d[i-1]]*k[i]*k[i-1]；

2.上節課不申請：f[0][i-1][j-1]+1.0*dis[d[i]][c[i-1]]*k[i]+1.0*dis[c[i]][c[i-1]]*(1-k[i])；

和上面分析一樣，上節課申請，可能的路徑有4條，不申請可能的路徑有兩條，乘上相應概率。

代碼：

#include <iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define LL long long?
const int N=2100;
const LL ?MAX=1e15;
double eps=1e-8;
long double f[2][N][N];//上i節課,換j節課，所需體力總和最小期望值
int n,m,v,e;
LL ?dis[310][310];
int c[N],d[N];
double k[N];
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++)
?? ?if(i!=j)
?? ?dis[i][j]=1e7; ? ? ? ??
?? ?for(int i=1;i<=e;i++)
?? ?{ ?int a,b,w;
?? ??? ?cin>>a>>b>>w;
?? ??? ?dis[a][b]=dis[b][a]=min(dis[a][b],(LL)w);
?? ?}
?? ?for(int o=1;o<=v;o++)
?? ?for(int i=1;i<=v;i++)
?? ?for(int j=1;j<=v;j++)
?? ?dis[i][j]=min(dis[i][j],dis[i][o]+dis[o][j]);?? ?
? ?for(int i=1;i<=n;i++)
? ?for(int j=0;j<=m;j++)
? ?f[0][i][j]=f[1][i][j]=1e7;
? ?f[0][1][0]=f[1][1][1]=0;
? ?for(int i=2;i<=n;i++)
? ?for(int j=0;j<=m&&j<=i;j++){
? ??? ?//cout<<i<<" "<<j<<endl;
? ??? ?f[0][i][j]=min(f[0][i-1][j]+dis[c[i]][c[i-1]],1.0*f[1][i-1][j]+
?? ? ? k[i-1]*dis[c[i]][d[i-1]]+1.0*(1-k[i-1])*dis[c[i]][c[i-1]]);
?? ? ? if(j>=1)
? ??? ?f[1][i][j]=min(f[0][i-1][j-1]+1.0*dis[d[i]][c[i-1]]*k[i]+1.0*dis[c[i]][c[i-1]]*(1-k[i])
?? ?,f[1][i-1][j-1]+1.0*dis[c[i]][c[i-1]]*(1-k[i])*(1-k[i-1])+1.0*dis[c[i]][d[i-1]]*(1-k[i])*k[i-1]
?? ?+1.0*dis[d[i]][c[i-1]]*k[i]*(1-k[i-1])+1.0*dis[d[i]][d[i-1]]*k[i]*k[i-1]);
? ?}
? ? long double ans=1e9;
? ? for(int i=0;i<=m;i++)
? ?ans=min(ans,min(f[0][n][i],f[1][n][i]));
? ?printf("%.2Lf\n",ans);
? ? return 0;
}
?