测试地址：聪聪和可可
做法：先用N次BFS预处理出p(i,j)：当聪聪在i，可可在j，轮到聪聪走时聪聪会选择的点，这个应该比较简单。然后我们再设f(i,j)为聪聪在i，可可在j，轮到聪聪走时聪聪抓到可可的期望步数，令to(i,k)为可可在i时下一步可能走到的点，可以得到：
f(i,j)=sigma(f(p(p(i,j),j),to(j,k))/(deg(j)+1))+1
之所以+1是因为sigma中算的状态要比f(i,j)多出一步，要先走一步才能到达这个状态，所以要+1。得出了状态转移方程后，就可以用记忆化搜索求解了，答案就是f(s,t)。
以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #define inf 999999999 using namespace std; int n,m,s,t,deg[1010],vd[1010],p[1010][1010]; double f[1010][1010]; int first[1010]={0},tot=0; struct edge {int v,next;} e[2010]; bool vis[1010]={0}; void insert(int a,int b) { e[++tot].v=b,e[tot].next=first[a],first[a]=tot; } void bfs(int s) { memset(vis,0,sizeof(vis)); memset(vd,-1,sizeof(vd)); queue<int> q; p[s][s]=s; vis[s]=1; vd[s]=0; for(int i=first[s];i;i=e[i].next) { p[s][e[i].v]=e[i].v; q.push(e[i].v); vis[e[i].v]=1; vd[e[i].v]=1; } while(!q.empty()) { int v=q.front();q.pop(); for(int i=first[v];i;i=e[i].next) if (vd[e[i].v]==-1||vd[e[i].v]==vd[v]+1) { vd[e[i].v]=vd[v]+1; p[s][e[i].v]=min(p[s][e[i].v],p[s][v]); if (!vis[e[i].v]) {vis[e[i].v]=1;q.push(e[i].v);} } } } double dp(int u,int v) { if (u==v) return 0; if (p[p[u][v]][v]==v) return 1; if (f[u][v]>0) return f[u][v]; double s=0; s+=dp(p[p[u][v]][v],v); for(int i=first[v];i;i=e[i].next) s+=dp(p[p[u][v]][v],e[i].v); s/=deg[v]+1; f[u][v]=s+1; return s+1; } int main() { scanf("%d%d",&n,&m); scanf("%d%d",&s,&t); for(int i=1,a,b;i<=m;i++) { scanf("%d%d",&a,&b); deg[a]++;deg[b]++; insert(a,b);insert(b,a); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) p[i][j]=inf; for(int i=1;i<=n;i++) bfs(i); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=0; printf("%.3lf",dp(s,t)); return 0; }
