题解 CF605E 【Intergalaxy Trips】

· · 题解

description

现在有 n 个点的有向完全图，边 (i,j) 出现的概率是 p_{i,j}，p_{i,i}=1，问从 1 到 n 的最短路的期望长度

假设这个人足够聪明

n\leq 1000

solution

这道题因为这个人足够聪明，所以他可以对于一个情况动态的做出决定

因为正着推不太好确定还需要几步能到，所以我们考虑从 n 倒着推，设 E_i 表示从 i 走到 n 的答案

考虑 E_i 的计算，对于 E_i 的所有出边 j ，显然只有当所有的 E_k<E_j 的 (i,k) 都没有出现的时候，我们才会考虑往 j 走。所以我们可以推出一个转移

E_i=\sum_{j=1}^nE_j\times p_{i,j}\times \prod_{k}^{E_k<E_j}(1-p_{i,k})

但是这个转移是有问题的。

因为可能存在一个情况，使得这个时候 i 没法走到其他的地方，这样的情况出现的概率是 \prod_{j}(1-p_{i,j})，但是这个时候因为 E_i 只计算的是非自环上的期望，所以转移应该写成

E_i=\sum_{j=1}^n\dfrac{E_j}{1-\prod_{k=1}^n (1-p_{j,k})}\times p_{i,j}\times \prod_{k}^{E_k<E_j}(1-p_{i,k})

考虑转移的顺序，显然在更新的时候，如果存在一个 E_k<E_j，并且还没有向那里走过，那么我们应该优先从 i 往 k 走。

所以我们可以每次枚举最小的之前没有更新过的 E_j 更新

这个做法和朴素的 \mathcal O(n^2) dijkstra 类似

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=1005;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n;
double g[N][N];
double E[N],prod[N];
bool vis[N];

int main()
{
    read(n);
    Rep(i,1,n)
        Rep(j,1,n){
            int x;
            read(x);
            g[i][j]=1.*x/100;
        }
    if(n==1)return puts("0"),0;
    vis[n]=true;
    for(int i=1;i<n;i++){
        E[i]=1;
        prod[i]=1-g[i][n];  
    }
    Rep(i,1,n){
        double low=1e18;
        int pos=0;
        Rep(j,1,n)
            if(!vis[j]&&E[j]/(1-prod[j])<low)
                low=E[j]/(1-prod[j]),pos=j;
        if(pos==1)return printf("%.10lf\n",E[1]/(1-prod[1])),0;
        vis[pos]=true;
        Rep(j,1,n)
            E[j]+=E[pos]/(1-prod[pos])*g[j][pos]*prod[j],prod[j]*=(1-g[j][pos]);
    }
    return 0;
}