这个题是个裸的期望dp，因为点比较少，所以可以用floyd，但是开始我打的dijkstra，t了，而且我发现数据还输不完，输着输着就停下了，换上floyd就好了……真是玄学
我们设dp[i][j][0/1]表示现在处理到了第i个教室，提交了j个申请，这个点是否提交申请
对于第三维是0的时候，我们只要考虑上个点交过申请还是没交过，但是当第3维为1的时候，我们还要考虑当前这个点申请通不通过和上个点的申请情况，有四种情况，比较难写，但是思维难度不大
总的来说这个题还是很有难度的，我觉得我考场上要是碰到这个题还是直接跳过吧qwq
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; int tail,x[2020],y[2020],a,b,c,head[330],n,m,v,e,ans[2020][2020]; double gai[2020],dp[2020][2020][2],pri; void floyd()//求最短路，预处理 {for(int k=1;k<=v;k++)for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)ans[i][j]=min(ans[i][j],ans[i][k]+ans[j][k]); } int main() {scanf("%d%d%d%d",&n,&m,&v,&e);for(int i=1;i<=n;i++)scanf("%d",&y[i]);for(int i=1;i<=n;i++)scanf("%d",&x[i]);for(int i=1;i<=n;i++)scanf("%lf",&gai[i]);memset(ans,0x3f,sizeof(ans));for(int i=1;i<=v;i++)ans[i][i]=0;for(int i=1;i<=e;i++)scanf("%d%d%d",&a,&b,&c),ans[a][b]=ans[b][a]=min(c,ans[b][a]);floyd();memset(dp,127,sizeof(dp));dp[0][0][0]=dp[1][0][0]=dp[1][1][1]=0;//初始化，一定要记得把dp[1][1][1]赋值为0！！！ for(int i=2;i<=n;i++)//一个点都不申请的时候 dp[i][0][0]=ans[y[i-1]][y[i]]+dp[i-1][0][0];for(int i=2;i<=n;i++)for(int j=1;j<=min(m,i);j++){dp[i][j][0]=min(dp[i-1][j][0]+ans[y[i-1]][y[i]],dp[i][j][0]);//当这个点不取的时候很简单，就看上一个点是否备取就行 dp[i][j][0]=min(dp[i-1][j][1]+(ans[x[i-1]][y[i]]*gai[i-1]+ans[y[i-1]][y[i]]*(1-gai[i-1])),dp[i][j][0]);dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+(ans[y[i-1]][x[i]]*gai[i]+ans[y[i-1]][y[i]]*(1-gai[i])));//当这个点取的时候，要考虑四种情况，a取/不取 b取/不取 dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+ans[x[i-1]][x[i]]*gai[i-1]*gai[i]+ans[x[i-1]][y[i]]*gai[i-1]*(1-gai[i])+ans[y[i-1]][x[i]]*gai[i]*(1-gai[i-1])+ans[y[i-1]][y[i]]*(1-gai[i])*(1-gai[i-1]));}pri=dp[n][0][0];for(int i=1;i<=m;i++)//取个最小值 pri=min(pri,min(dp[n][i][0],dp[n][i][1]));printf("%.2lf",pri); }