YbtOJ 454「概率期望 dp」期望旅行
题目链接：YbtOJ #454
小 A 有一张 n 个点的有向图。
已知图中 xrightarrow y 的有向边每天有 a_{x,y} 的概率存在。保证 forall x,a_{x,x}=1，即所有自环肯定存在。
小 A 从 1 号点出发，每天需要选择当前所在点一条 存在 的出边，走到对应的点。
求采取最优策略时，从 1 号点走到 n 号点的期望天数。
1le nle 3times10^3，0le a_{i,j}le 1
Solution
设 E(x) 表示 采取最优策略时，从 x 走到 n 的期望步数。
假设对于一个点 x，已知有 k 个点 y_1,y_2,…,y_k 满足 E(y_1)le E(y_2)le…le E(y_k)le E(x)。
显然贪心地去考虑，必然是尽可能走到 y_1，次优是走到 y_2，以此类推。
所以我们可以倒着做，记 s_x=sum_{i=1}^k(E(y_i) 1)times a_{x,y_i}timesprod_{j=1}^{i-1}(1-a_{x,y_j})，表示 离开 x 到 n 的期望天数。
记 p_x=prod_ik(1-a_{x,y_i})，表示 不会离开 x 的概率。
那么 E(x) 的计算就很简单了，只需分是否离开两种情况，得到 E(x)=p_x(E(x) 1) s_x，化简即 E(x)=frac{s_x p_x}{1-p_x}。
直接暴力类似 Dijkstra 转移即可。
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
Cn int N=3e3 10;
int n,vis[N];
double a[N][N],s[N],e[N],E[N];
int main(){
freopen("trip.in","r",stdin),freopen("trip.out","w",stdout);
RI i,j,u;for(scanf("%d",&n),i=1;i<=n;i ) for(j=1;j<=n;j ) scanf("%lf",&a[i][j]);
auto CL=[&]() -> void{RI i;for(i=1;i<=n;i ) !vis[i]&&(e[i]=0.0,s[i]=1.0);};
auto CT=[&](CI x) -> void{RI i;for(i=1;i<=n;i ) !vis[i]&&(e[i] =(E[x] 1)*a[i][x]*s[i],s[i]*=1.0-a[i][x]);};
auto CP=[&]() -> void{RI i;for(E[u=0]=2e9,i=1;i<=n;i ) !vis[i]&&(E[i]=(s[i] e[i])/(1.0-s[i]),E[i]<E[u]&&(u=i));};
CL(),u=n;W(u) vis[u]=1,CT(u),CP();return printf("%.8lfn",E[1]),0;
}
