链接

• 类似于开车旅行，如果老鼠确定了那么猫的路线是确定的。
• 预处理\(g_{i,j}\)表示老鼠在\(i\)号点，猫的下一步方向，\(Bfs\)就行了
• 设\(f_{i,j}\)表示老鼠在\(i\)，猫\(j\)的期望步，转移枚举出边状态即可。
• 至于为什么这样的转移不会成环？
• 因为猫始终是顺着老鼠的方向走的，老鼠每次走一步，猫每次走两步，也就是两者距离单调不升，又因为老鼠一直在走，所以转移关系不会成环，一定是拓扑关系。

#include
    
     #define R register int#define db double using namespace std;const int N=2002;int n,m,s,t,u,v,cnt,hd[N],to[N],nt[N];int g[N][N],vis[N],Dis[N],du[N],rec[N][N];db f[N][N];void link(R f,R t){nt[++cnt]=hd[f],to[cnt]=t,hd[f]=cnt;}int gi(){    R x=0,k=1;char c=getchar();    while(c!='-'&&(c<'0'||c>'9'))c=getchar();    if(c=='-')k=-1,c=getchar();    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();     return x*k;}queue
     
      Q;void Bfs(R s){    while(!Q.empty())Q.pop();    for(R i=1;i<=n;++i)Dis[i]=1e9,vis[i]=0;    Dis[s]=0,vis[s]=1,Q.push(s),Dis[n+1]=1e9;    while(!Q.empty()){        R i=Q.front();Q.pop();        for(R k=hd[i];k;k=nt[k]){            if(vis[to[k]])continue;            if(Dis[to[k]]>Dis[i]+1)                Dis[to[k]]=Dis[i]+1,Q.push(to[k]);        }    }    for(R i=1;i<=n;++i)        if(i!=s){            g[s][i]=n+1;            for(R k=hd[i];k;k=nt[k])                if(Dis[to[k]]