令人印象深刻的状态转移方程...
f[i][j][0/1]表示前i个换j次，第i次是否申请时的期望。
注意可能有重边，自环。
转移要分类讨论，距离是上/这次成功/失败的概率乘相应的路程。
从上次的0/1中取min
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = , M = ;
const double INF = 1.0 * 0x3f3f3f3f; inline void read(int &x) {
x = ;
char c = getchar();
while(c > '' || c < '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} int G[N][N], a[M], b[M];
double k[M], f[M][M][]; int main() {
int n, m, v, e;
read(n);
read(m);
read(v);
read(e);
for(int i = ; i <= n; i++) {
read(a[i]);
}
for(int i = ; i <= n; i++) {
read(b[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lf", &k[i]);
}
int x, y, z;
memset(G, 0x3f, sizeof(G));
for(int i = ; i <= e; i++) {
read(x);
read(y);
read(z);
if(G[x][y]) {
G[y][x] = G[x][y] = std::min(G[x][y], z);
}
else {
G[x][y] = G[y][x] = z;
}
} /// floyd
for(int i = ; i <= v; i++) {
G[i][i] = ;
}
for(int p = ; p <= v; p++) {
for(int i = ; i <= v; i++) {
for(int j = ; j <= v; j++) {
G[i][j] = std::min(G[i][j], G[i][p] + G[p][j]);
}
}
} for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
f[i][j][] = f[i][j][] = INF;
}
}
f[][][] = f[][][] = ;
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
f[i][j][] = std::min(f[i - ][j][] + G[a[i - ]][a[i]],
f[i - ][j][]
+ G[b[i - ]][a[i]] * k[i - ]
+ G[a[i - ]][a[i]] * ( - k[i - ]));
if(j) {
f[i][j][] = std::min(f[i - ][j - ][]
+ G[a[i - ]][b[i]] * k[i]
+ G[a[i - ]][a[i]] * ( - k[i]),
f[i - ][j - ][]
+ G[b[i - ]][b[i]] * k[i - ] * k[i]
+ G[b[i - ]][a[i]] * k[i - ] * ( - k[i])
+ G[a[i - ]][b[i]] * ( - k[i - ]) * k[i]
+ G[a[i - ]][a[i]] * ( - k[i - ]) * ( - k[i]));
}
}
} double ans = INF; for(int i = ; i <= m; i++) {
ans = std::min(ans, f[n][i][]);
ans = std::min(ans, f[n][i][]);
}
printf("%.2lf", ans); return ;
}
AC代码
我一开始把ans初值设的是0...