正题
题目链接:https://www.luogu.com.cn/problem/CF605E
题目大意
给出\(n\)个点的一张完全有向图，每一天\(i\)到\(j\)的路径有\(p_{i,j}\)的概率出现。
询问从\(1\)出发走到\(n\)在最优策略下的期望天数。
\(1\leq n\leq 10^3,p_{i,i}=1\)
解题思路
设\(g_i\)表示从\(i\)到\(n\)的答案，那么\(g\)满足式子
\[g_i=\sum_{j=1}^{n}\frac{g_{j}}{\prod_{g_k<g_j}(1-p_{j,k})}\times p_{i,j}\times \prod_{g_k<g_j}(1-p_{i,k})
\]
注意到里面有条件\(g_k<g_j\)，但是我们并不知道\(g\)，好像就死循环了。
但是我们可以知道\(g_n\)肯定是最小的而且是\(0\)，然后剩下第二小的只会受到\(g_n\)的影响，也就是这个里面有一个的\(g\)是完整的。
可以猜测这个第二小的肯定是剩下的\(g\)里面最小的那个，因为如果不是，那么显然不满足我们最小化的条件，从一个更大的走到了本应该可以更小的。
所以我们每次剩下的点中找到一个最小的\(\frac{g_{j}}{\prod_{g_k<g_j}(1-p_{j,k})}\)来更新它对其他点的影响即可。
时间复杂度\(O(n^2)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1100;
int n;bool v[N];
double p[N][N],prod[N],f[N];
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.0;
}
}
if(n==1)return puts("0")&0;
for(int i=1;i<n;i++)
prod[i]=1-p[i][n],f[i]=1;
v[n]=1;
while(1){
double low=1e9;int x;
for(int i=1;i<=n;i++)
if(f[i]/(1-prod[i])<low&&!v[i])
low=f[i]/(1-prod[i]),x=i;
if(x==1)return printf("%.10lf",low)&0;
v[x]=1;
for(int i=1;i<=n;i++){
if(v[i])continue;
f[i]+=low*p[i][x]*prod[i];
prod[i]*=(1-p[i][x]);
}
}
return 0;
}