题解 CF605E 【Intergalaxy Trips】

CF605E

Solution

设E(u)表示从u到n的期望步数，考虑下一步，如果是走到v且E(v)\geq E(u)，那么当前这一步的最优策略肯定是停在原地。

所以我们永远不会走到一个比当前期望步数大的点，所以我们可以考虑将所有答案按从小到大的顺序算出，并以此扩展。

设u的后继分别为v_i且E非降，那么

后面的\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

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;
}