题目链接：

题解：完全不会写有关期望的问题，怎么办嘞。。。。

首先因为每次聪聪都会往离可可最短的路走，我们先用求出p[i][j]（其实就是拓扑。。。）来表示从i节点到j节点走最短路到达的第一个节点。

然后每次都dfs聪聪下一步可能会走的节点，只要有哪一层p[i][j]==j或p[p[i][j]][j]==j（因为聪聪能走两步）就返回1，可可一定会被聪聪抓到，用now表示p[p[i][j]][j]；

f[i][j]=sum(f[now][j])/(可可可以走的方案数，即出边的数量加1)+1（为什么要在最后加1呢？因为我们首先需要走到now这个节点）；

下面是具体程序

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct ding{    int to,next;}edge[5000];int n,head[2000],deg[2000],cnt,dis[2000],p[2000][2000];double f[2000][2000];void add(int u,int v) {  edge[++cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; deg[u]++;//用deg[i]来储存出边}void bfs(int s){//我们假设以当前节点为根，因为这是一棵树，所以保证先更新的点一定是后更新的点的父节点，即父节点的值若已被更新就不会因后面的改变而改变  queue
         
          q;  q.push(s);  memset(dis,-1,sizeof dis);  dis[s]=0;  while (!q.empty())  {      int now=q.front(),tmp=p[s][now];      q.pop();      for (int i=head[now];i;i=edge[i].next)      {        int y=edge[i].to;        if ((dis[y]==-1)||((dis[now]+1==dis[y])&&(tmp
          
           0) return f[s][t]; if (s==t) return 0; if ((p[s][t]==t)||(now==t)) return f[s][t]=1; double sum=dp(now,t); for (int i=head[t];i;i=edge[i].next) sum+=dp(now,edge[i].to); return f[s][t]=sum/(deg[t]+1)+1;}int main(){ int m,a,b,x,y; scanf("%d%d%d%d",&n,&m,&a,&b); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x);//正向反向都要加 } for (int i=1;i<=n;i++) bfs(i); //处理出i这个点到其他店的最短路 printf("%0.3lf\n",dp(a,b)); return 0;}