题目
思路
期望dp。不会参考的ViXbob的题解
设 (dp[i][j][0/1]) 为前 (i) 节课，申请调了 (j) 节课的最小期望，第三维的 (0) 表示第 (i) 节课不申请调，(1) 表示申请调。
(a[i]) 表示第 (i) 节课原本的上课场所，(b[i]) 表示第 (i) 节课调整之后的上课场所。(dis[i][j]) 表示教室 (i) 到教室 (j) 的最短路径长度。
(dp[i][j][0]=minegin{cases} dp[i-1][j][0]+dis[a[i-1]][a[i]] \[2ex] dp[i-1][j][1]+dis[b[i-1]][a[i]] * k[i-1]+dis[a[i-1]][a[i]] * (1-k[i-1])end{cases})
(dp[i-1][j][0] + dis[a[i-1]][a[i]]) 表示前 (i-1) 节课，申请调了 (j) 节课且第 (i-1) 节课没有申请调的最优情况加上 (dis[a[i-1]][a[i]]) ，因为第 (i) 节课不申请调所以第 (i) 节课还是在 (a[i]) 上，(a[i-1]) 同理。
(dp[i-1][j][1]+dis[b[i-1]][a[i]] * k[i-1] + dis[a[i-1]][a[i]] * (1-k[i-1])) 表示前 (i-1) 节课，调了 (j) 节课且第 (i-1) 节课申请调了的最优情况加上 (dis[b[i-1]][a[i]] * k[i-1])（申请调，并且通过的期望）再加上 (dis[a[i-1]][a[i]] * (1-k[i-1]))（申请调，但是没通过的期望）。
(dp[i][j][1]=minegin{cases} dp[i-1][j-1][0]+dis[a[i-1]][a[i]]*(1-k[i])+dis[a[i-1]][b[i]]*k[i] \[2ex] dp[i-1][j-i][1]+dis[a[i-1]][a[i]]*(1-k[i-1])*(1-k[i])+dis[a[i-1]][b[i]]*(1-k[i-1])*k[i]+dis[b[i-1]][a[i]]*k[i-1]*(1-k[i])+dis[b[i-1]][b[i]]*k[i-1]*k[i] end{cases})
(dp[i][j][1]) 的状态转移方程与 (dp[i][j][0]) 类似，不讲了（我懒）。
跑 v 遍堆优化 Dijkstra 慢死了，不开 O2 过不了（可能是我写的太丑了/kk），Floyd 跑的快点。
Code
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<queue>
#define MAXN 2001
#define inf 2147483647
inline void read(int &T) {
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
typedef std::pair<int,int> pii;
std::priority_queue<pii,std::vector<pii>,std::greater<pii> >q;
int n,m,v,e,pthn,head[301],a[MAXN],b[MAXN],dis[301][301];
double ans=inf*114514.0,k[MAXN],dp[MAXN][MAXN][2];
bool vis[301];
struct Edge {
int next,to,w;
}pth[90001<<1];
void add(int from,int to,int w) {
pth[++pthn].to=to,pth[pthn].next=head[from];
pth[pthn].w=w,head[from]=pthn;
}
double min(double a,double b) {
return a<b?a:b;
}
void dij(int s) {
memset(vis,0,sizeof vis);
for(int i=0;i<=v;++i) dis[s][i]=inf;
dis[s][s]=0;
q.push(std::make_pair(dis[s][s],s));
while(!q.empty()) {
pii u=q.top();q.pop();
if(vis[u.second]) continue;
vis[u.second]=1;
for(int i=head[u.second];i;i=pth[i].next) {
int x=pth[i].to;
if(!vis[x]&&dis[s][x]>u.first+pth[i].w) {
dis[s][x]=dis[s][u.second]+pth[i].w;
q.push(std::make_pair(dis[s][x],x));
}
}
}
}
int main() {
read(n),read(m),read(v),read(e);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i) read(b[i]);
for(int i=1;i<=n;++i) scanf("%lf",&k[i]);
for(int i=1,x,y,w;i<=e;++i) {
read(x),read(y),read(w);
add(x,y,w),add(y,x,w);
}
for(int i=1;i<=v;++i) dij(i);
for(int i=1;i<=v;++i) dis[0][i]=dis[i][0]=0;
for(int i=0;i<=n;++i) {
for(int j=0;j<=m;++j) {
dp[i][j][0]=dp[i][j][1]=inf*114514.0;
}
}
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]+dis[a[i-1]][a[i]];
for(int j=1;j<=min(i,m);++j) {
dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+dis[a[i-1]][a[i]],dp[i-1][j][1]+dis[b[i-1]][a[i]]*k[i-1]+dis[a[i-1]][a[i]]*(1-k[i-1])));
dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+dis[a[i-1]][b[i]]*k[i]+dis[a[i-1]][a[i]]*(1-k[i]),dp[i-1][j-1][1]+dis[b[i-1]][b[i]]*k[i]*k[i-1]+dis[b[i-1]][a[i]]*(1-k[i])*k[i-1]+dis[a[i-1]][b[i]]*(1-k[i-1])*k[i]+dis[a[i-1]][a[i]]*(1-k[i-1])*(1-k[i])));
}
}
for(int i=0;i<=m;++i) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
printf("%.2lf
",ans);
return 0;
}