首先，猫的走位太飘了……只能预处理……
先对每一个点跑一遍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<bits/stdc++.h> 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<class T>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 num 16 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)const 30 {return dis>b.dis;} 31 }; 32 priority_queue<node> 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 ",dfs(s,t)); 74 return 0; 75 }