题目链接：聪聪和可可
一道水题……开始还看错题了，以为边带权……强行\(O(n^3)\)预处理……
首先，我们显然可以预处理出一个数组\(p[u][v]\)表示可可在点\(u\)，聪聪在点\(v\)的时候聪聪下一步会往哪里走。然后……一个记忆化搜索就轻易地解决掉了……
至于转移方程吗，我觉得也没有必要写了……你要是实在不知道就看一看代码吧……
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 1010 using namespace std;
typedef double llg; int n,E,C,M,dis[N],p[N][N],fr[N],d[N],ld;
int head[N],next[N<<1],to[N<<1],tt,du[N];
llg f[N][N]; bool vis[N],w[N][N]; void solve(int S){
for(int i=1;i<=n;i++) dis[i]=vis[i]=0;
vis[S]=1; d[ld=1]=S; du[S]++;
for(int l=1,u;u=d[l],l<=ld;l++)
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]) dis[v]=dis[u]+1,vis[v]=1,d[++ld]=v,fr[v]=u;
else if(dis[v]==dis[u]+1) fr[v]=min(fr[v],u);
for(int i=1;i<=n;i++) p[S][i]=fr[i];
} llg search(int u,int v){
if(w[u][v]) return f[u][v];
if(p[u][v]==u || p[u][p[u][v]]==u) return 1;
w[u][v]=1;
for(int i=head[u];i;i=next[i])
f[u][v]+=search(to[i],p[u][p[u][v]])+1;
f[u][v]+=search(u,p[u][p[u][v]])+1;
return f[u][v]/=(llg)du[u];
} int main(){
File("a");
scanf("%d %d %d %d",&n,&E,&C,&M);
for(int i=1,x,y;i<=E;i++){
scanf("%d %d",&x,&y); du[x]++; du[y]++;
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
}
for(int i=1;i<=n;i++) solve(i),w[i][i]=1;
printf("%.3lf",search(M,C));
return 0;
}