meaning of the title：There are V classrooms. E has the right to have no edges (to ensure all classrooms are connected).
First there are n time periods, each time period, Niu Niu (volume.) Going to class $c_i$for class.
After class, he has to go to $c_{i+1}$for the next class.
At present, cattle can apply for m times, change the classroom, make the road less.
If I is applied to the time segment, the probability of $p_i$is changed to $d_i$with a probability of $c_i$(failure is equal to no change).
Of course, he can apply less or even apply.
Now, find out the minimum expectation of cattle distance.
Input: n，m，v，e Time limit, number of applications, number of classrooms, edges
The next three lines are $c_i\ \ d_i \ \ p_i$.
And then the edge
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
Output 2.80 (two decimal places)
Special properties of 1: graph on any two points $a_i, b_i, a_i, b_i$There is a path that consumes the least energy and contains only one road.
Special properties 2: for all $1 less than i i n, k_i= 1$ 。
See this question, obviously expect DP ah. I set the state f[i][j] to represent the first I time period, and applied the j distance expectation. However,… QAQ can’t write it out.
Last fight violence: DFS set dfs40 points (find all cases).
However, the preprocessing is right: Floyd handles two classroom distances.
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define DB double int n; int m; int f[350][350]; int app[2050]; int huan[2050]; DB gl[2050]; bool vis[2050]; int road[550]; bool ok[2050]; int v; int e; int cnt; DB tot; double ans=0x7fffffff; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void Floyd() { for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) if(i!=j&&j!=k&&k!=i) f[i][j]=min(f[i][k]+f[k][j],f[i][j]); for(int i=1;i<=v;i++) f[i][i]=0; // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // cout<<i<<" "<<j<<" "<<f[i][j]<<endl; } inline void ddfs(int step,DB g) { if(step==n+1) { DB dis=0; for(int i=1;i<=n;i++) { if(vis[i]&&ok[i]) road[i]=huan[i]; else road[i]=app[i]; } for(int i=2;i<=n;i++) dis+=f[road[i]][road[i-1]]; tot+=dis*g; return; } if(vis[step]) { ok[step]=true; ddfs(step+1,g*gl[step]); ok[step]=false; ddfs(step+1,g*(1-gl[step])); } else ddfs(step+1,g); } inline void dfs(int step,int num,DB g) { if(step==n+1) { tot=0; ddfs(1,g); ans=min(ans,tot); return; } if(num<m) { vis[step]=true; dfs(step+1,num+1,g); vis[step]=false; } dfs(step+1,num,g); } signed main() { in(); n=read(); m=read(); v=read(); e=read(); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) app[i]=read(); for(int i=1;i<=n;i++) huan[i]=read(); for(int i=1;i<=n;i++) scanf("%lf",&gl[i]); for(int x,y,z,i=1;i<=e;i++) { x=read(); y=read(); z=read(); f[x][y]=f[y][x]=z; } Floyd(); dfs(1,0,1); printf("%.2lf",ans); out(); return 0; }
100Positive solutions: (of course, expect DP)
Using dp[i][j][0/1] to represent the former I classrooms, applied for J times. Has I changed in classrooms?
（Why not treat dp[1][1][0] and dp[1][0][1] in a special way? Reason: the former can be transferred to the latter as an illegitimate state, QAQ).
First consider the situation of no change, that is, when $k = 0$.
$C1 = c[i – 1], C2 = d[i – 1], C3 = c[i], C4 = d[i]$
$mp[i][j]$Represents the shortest path between $i and j$.
$dp[i][j][0] =min\begin{cases} dp[i – 1][j][0] + mp[C1][C3]\\dp[i – 1][j][1] + mp[C1][C3] * (1 – k[i – 1]) + mp[C2][C3] * k[i – 1]\end{cases}$
Obviously, if you don’t change classrooms at $i-1, $i-1 to $i, there’s only one case where you don’t change classrooms. If you change classrooms at $i-1, there are two cases where $i-1 is successful, or if you don’t, so that’s the probability of the corresponding path length multiplier.
$dp[i][j][1] =min\begin{cases} dp[i – 1][j – 1][0] + mp[C1][C3] * (1 – k[i]) + mp[C1][C4] * k[i]\\dp[i – 1][j – 1][1] + mp[C2][C4] * k[i] * k[i – 1] + mp[C2][C3] * k[i – 1] * (1 – k[i]) + mp[C1][C4] * (1 – k[i – 1]) * k[i] + mp[C1][C3] * (1 – k[i – 1]) * (1 – k[i])\end{cases} $
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define DB double int n; int m; int f[350][350]; int app[2050]; int huan[2050]; DB gl[2050]; double dp[2050][2050][2]; int v; int e; int cnt; DB tot; double ans=0x7fffffff; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void Floyd() { for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) f[i][j]=min(f[i][k]+f[k][j],f[i][j]); for(int i=1;i<=v;i++) f[i][0]=f[0][i]=f[i][i]=0; } signed main() { // in(); n=read(); m=read(); v=read(); e=read(); memset(f,60,sizeof f); memset(dp,0x5f,sizeof dp); for(int i=1;i<=n;i++) app[i]=read(); for(int i=1;i<=n;i++) huan[i]=read(); for(int i=1;i<=n;i++) scanf("%lf",&gl[i]); for(int x,y,z,i=1;i<=e;i++) { x=read(); y=read(); z=read(); f[x][y]=f[y][x]=min(f[x][y],z); } Floyd(); dp[1][0][0]=0; dp[1][1][1]=0; for(int i=2;i<=n;i++) { dp[i][0][0]=dp[i-1][0][0]+f[app[i]][app[i-1]]; for(int j=1;j<=min(m,i);j++) { dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+f[app[i]][app[i-1]],dp[i-1][j][1]+f[huan[i-1]][app[i]]*gl[i-1]+f[app[i-1]][app[i]]*(1-gl[i-1]))); dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+f[app[i-1]][huan[i]]*gl[i]+f[app[i-1]][app[i]]*(1-gl[i]),dp[i-1][j-1][1]+f[app[i-1]][app[i]]*(1-gl[i-1])*(1-gl[i])+f[huan[i-1]][app[i]]*gl[i-1]*(1-gl[i])+f[app[i-1]][huan[i]]*(1-gl[i-1])*gl[i]+f[huan[i-1]][huan[i]]*gl[i-1]*gl[i])); } } for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1])); printf("%.2lf",ans); out(); return 0; }