题解 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 类似 ```cpp #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; } ```