题解 CF605E 【Intergalaxy Trips】
关怀他人
2021-01-27 23:14:34
### CF605E
#### Solution
设$E(u)$表示从$u$到$n$的期望步数，考虑下一步，如果是走到$v$且$E(v)\geq E(u)$，那么当前这一步的最优策略肯定是停在原地。
所以我们永远不会走到一个比当前期望步数大的点，所以我们可以考虑将所有答案按从小到大的顺序算出，并以此扩展。
设$u$的后继分别为$v_i$且$E$非降，那么
$$
E(u)=\sum_i \dfrac{E(v_i)}{1-\prod_{j=1}^n(1-p_{v_i,j})}p_{u,v_i}\prod_{j=1}^{i-1} (1-p_{u,v_j})+1
$$
后面的$\prod_{j=1}^{i-1} (1-p_{u,v_j})$表示$v_i$可以走且所有期望步数小于$v_i$的都不能走，而前面除以$1-\prod_{j=1}^n(1-p_{v_i,j})$的原因是要去掉$v_i$没法走到其他地方的概率，因为$E_i$计算的是不考虑自环的概率，最后再加上当前这一步的贡献$1$即可。
用类似 $\mathrm{dijkstra}$ 的方式每次取最小的转移即可。
时间复杂度 $\mathcal O(n^2)$
#### Code
```cpp
int n;
int vis[MAXN],a[MAXN];
double p[MAXN][MAXN],E[MAXN],prod[MAXN];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
scanf("%lf",&p[i][j]), p[i][j] /= 100;
if(n == 1) {printf("0\n"); return 0;}
for(int i = 1;i <= n;i++) E[i] = 1, prod[i] = 1 - p[i][n];
vis[n] = 1; a[1] = n;
for(int i = 1;i <= n;i++){
double minval = llINF; int pos = 0;
for(int j = 1;j <= n;j++){
if(!vis[j] && E[j] / (1 - prod[j]) < minval){
pos = j;
minval = E[j] / (1 - prod[j]);
}
}
vis[pos] = 1;
for(int j = 1;j <= n;j++)
E[j] += E[pos] / (1 - prod[pos]) * p[j][pos] * prod[j], prod[j] *= (1 - p[j][pos]);
}
printf("%.8f\n",E[1] / (1 - prod[1]));
return 0;
}
```