首先，猫的走位太飘了……只能预处理……

先对每一个点跑一遍dijkstra跑出最短路，然后再预处理出$nxt[i][j]$表示当猫在$i$老鼠在$j$时猫下一步会走到哪里

然后考虑dp，设$dp[i][j]$表示猫在$i$老鼠在$j$时猫抓到老鼠的期望步数是多少

如果$i==j$，那么$dp[i][j]=0$

如果猫一步或两步可以到达老鼠，那么$dp[i][j]=1$

否则的话，猫肯定会走两步，设$sec$表示猫走两步到达的位置，则$dp[i][j]=1+\sum dp[sec][k]/(p[j]+1)$，（其中$sec$表示猫走两步到达的点，$p[j]$表示点$j$的度数，$k$表示$j$可以到达的位置（含原地））

那么这个东西可以用一个记忆化搜索解决

最后的答案就是$dp[s][t]$

1 //minamoto 2 #include
     
       3 #define inf 0x3f3f3f3f 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template
      
       inline bool cmin(T&a,const T&b){
   return a>b?a=b,1:0;} 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 const int N=1005;19 int head[N],Next[N<<1],ver[N<<1],tot;20 inline void add(int u,int v){21     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;22 }23 int dis[N][N],vis[N],p[N],nxt[N][N];double dp[N][N];24 int n,m,s,t;25 struct node{26     int u,dis;27     node(){}28     node(int u,int dis):u(u),dis(dis){}29     inline bool operator <(const node &b)const30     {
   return dis>b.dis;}31 };32 priority_queue
       
         q;33 void dijkstra(int *dis,int s){34     q.push(node(s,0)),dis[s]=0;35     memset(vis,0,sizeof(vis));36     while(!q.empty()){37         int u=q.top().u;q.pop();38         if(vis[u]) continue;39         vis[u]=1;40         for(int i=head[u];i;i=Next[i]){41             int v=ver[i];42             if(cmin(dis[v],dis[u]+1))43             q.push(node(v,dis[v]));44         }45     }46 }47 double dfs(int s,int t){48     if(dp[s][t]!=-1) return dp[s][t];49     if(s==t) return 0;50     int fir=nxt[s][t],sec=nxt[fir][t];51     if(fir==t||sec==t) return 1;52     dp[s][t]=1;53     for(int i=head[t];i;i=Next[i]){54         int v=ver[i];55         dp[s][t]+=dfs(sec,v)/(p[t]+1);56     }57     dp[s][t]+=dfs(sec,t)/(p[t]+1);58     return dp[s][t];59 }60 int main(){61 //    freopen("testdata.in","r",stdin);62     n=read(),m=read(),s=read(),t=read();63     for(int i=1,u,v;i<=m;++i)64     u=read(),v=read(),add(u,v),add(v,u),++p[u],++p[v];65     for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j]=nxt[i][j]=inf,dp[i][j]=-1;66     for(int i=1;i<=n;++i) dijkstra(dis[i],i);67     for(int i=1;i<=n;++i)68     for(int e=head[i];e;e=Next[e]){69         int v=ver[e];70         for(int j=1;j<=n;++j)71         if(dis[i][j]==dis[v][j]+1) cmin(nxt[i][j],v);72     }73     printf("%.3lf\n",dfs(s,t));74     return 0;75 }