最后一次参NOIP的时候的day1t3，当时就没能AC出来，没想到过了三年最终还是要因为练习最短路而写这题。
这就是善恶终有报苍天饶过谁吗。
题目描述略，总体来说就是个DP（顺便使用最短路预处理），对于期望的运用也是很基础的部分。当年考场上我要是没被期望吓傻应该能够A掉这题吧
DP[i][j][0]表示第i个时间段，换了j次教室，当前不换教室。DP[i][j][1]表示当前申请换教室。
那么DP[i][j][0]可以从DP[i-1][j][0]和DP[i-1][j][1]转移而来，DP[i][j][1]可以从DP[i-1][j-1][0]和DP[i-1][j-1][1]中转移而来。
具体的转移方程式太麻烦不写了，仔细思考就OK，不是很难。
最开始使用Floyd预先跑个全源最短路预处理，这就是本题的最短路部分吧（悲）
不卡精度非常良心。
那么下面是代码。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const double INF=1e10; int n,m,v,e; int dis[305][305]={0},A[2005]={0},B[2005]={0}; double pos[2005],DP[2005][2005][3]; void Floyd(); void WriteIn(); int main(void) { memset(dis,127/2,sizeof(dis)); WriteIn(); Floyd(); for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) DP[i][j][1]=DP[i][j][0]=INF; DP[1][0][0]=0; DP[1][1][1]=0; double tmp; for(int i=2;i<=n;i++) { for(int j=0;j<=m;j++) { DP[i][j][0]=min(DP[i][j][0],DP[i-1][j][0]+dis[A[i-1]][A[i]]); DP[i][j][0]=min(DP[i][j][0],DP[i-1][j][1]+dis[A[i-1]][A[i]]*(1.0-pos[i-1])+dis[B[i-1]][A[i]]*pos[i-1]); if(!j)continue; DP[i][j][1]=min(DP[i][j][1],DP[i-1][j-1][0]+dis[A[i-1]][A[i]]*(1.0-pos[i])+dis[A[i-1]][B[i]]*pos[i]); tmp=dis[A[i-1]][A[i]]*(1.0-pos[i])*(1.0-pos[i-1])+dis[A[i-1]][B[i]]*pos[i]*(1-pos[i-1]); tmp+=dis[B[i-1]][A[i]]*(1.0-pos[i])*pos[i-1]+dis[B[i-1]][B[i]]*pos[i]*pos[i-1]; DP[i][j][1]=min(DP[i][j][1],DP[i-1][j-1][1]+tmp); } } double ans=INF; for(int i=0;i<=m;i++) { ans=min(ans,DP[n][i][1]); ans=min(ans,DP[n][i][0]); } printf("%.2f",ans); return 0; } void WriteIn() { scanf("%d%d%d%d",&n,&m,&v,&e); int a,b,c; 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",&pos[i]); for(int i=1;i<=v;i++)dis[i][i]=0; for(int i=1;i<=e;i++) { scanf("%d%d%d",&a,&b,&c); dis[a][b]=min(dis[a][b],c); dis[b][a]=min(dis[a][b],c); } return; } void Floyd() { 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]); return; }