题意
给定一张 \(n\) 个节点 \(m\) 条边的无向图，初始时，A_zjzj 在 \(S\)，fxt 在 \(T\)，现在 A_zjzj 要前去抓住 fxt。
-
A_zjzj 只会往使得两人的最短距离减 \(1\) 的点前进，如果有多个这样的点，他会走编号最小的一个节点。
-
如果 A_zjzj 在走完这一步后并没有抓住 fxt，那么他在这一秒内还会重复执行上述动作。
-
当 A_zjzj 走完以后，fxt 会等概率走向相邻的节点或停留在原地不动。
上述操作均在一秒钟内进行，求 A_zjzj 抓住 fxt 的期望时间。
\(1 \leq n,m \leq 1000\)。
思路
由于边权都为 \(1\)，可以对每个节点 bfs 一遍预处理出任意两点的最短距离，时间复杂度为 \(O(n(n+m))\)。
设 \(p_{u,v}\) 为 A_zjzj 在 \(u\) 节点，fxt 在 \(v\) 节点时 A_zjzj 接下来会走到的节点。这一部分也可以预处理得出。
设 \(p_{P_{u,v},v}=x\)，即 A_zjzj 走两步以后会到达的节点。设 \(f_{u,v}\) 为 A_zjzj 在 \(u\) 节点，fxt 在 \(v\) 节点时的答案。令 \(d_u\) 为与 \(u\) 相邻的节点个数，那么可以得出转移方程：
\[f_{u,v}=\dfrac{f_{x,v}+\sum_{k \in son_v} f_{x,k}}{d_u+1} \]由于 A_zjzj 只会往特点的节点走，所以这里不会出现成环的情况，于是只需要记忆化搜索即可。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,M=2023;
int q[N],h[N],idx,n,m,p[N][N],d[N][N];double f[N][N];
struct edge{int v,nex;}e[M];
void add(int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
void bfs(int S)
{
int hh=0,tt=-1;q[++tt]=S;memset(d[S],0x3f,sizeof(d[S]));d[S][S]=0;
while(hh<=tt)
{
int u=q[hh++];
for(int i=h[u];i;i=e[i].nex)
{
int v=e[i].v;if(d[S][v]<=d[S][u]+1) continue;
d[S][v]=d[S][u]+1;q[++tt]=v;
}
}
}
double dp(int u,int T)
{
if(u==T) return f[u][T]=0.0;
if(p[u][T]==T||p[p[u][T]][T]==T) return f[u][T]=1.0;
if(f[u][T]!=0.0) return f[u][T];f[u][T]=dp(p[p[u][T]][T],T);int cnt=1;
for(int i=h[T];i;i=e[i].nex)
{
int v=e[i].v;f[u][T]+=dp(p[p[u][T]][T],v);cnt++;
}
f[u][T]/=1.0*cnt;return f[u][T]+=1.0;
}
int main()
{
scanf("%d%d",&n,&m);int S,T;scanf("%d%d",&S,&T);
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(int i=1;i<=n;i++) bfs(i);memset(p,0x3f,sizeof(p));
for(int u=1;u<=n;u++)
for(int i=h[u];i;i=e[i].nex)
for(int j=1;j<=n;j++)
if(d[u][j]==d[e[i].v][j]+1) p[u][j]=min(p[u][j],e[i].v);
printf("%.3lf\n",dp(S,T));
return 0;
}