[NOI2005]聪聪与可可

首先是猫的走路方式与老鼠的位置有关，点数又比较少，所以我们可以预处理 \(d_{i,j}\) 表示猫在 \(i\)，老鼠在 \(j\) 时猫下一步的位置。

这样不确定的东西都集中到了老鼠身上。

设 \(f_{i,j}\) 表示猫在 \(i\)，老鼠在 \(j\) 时猫吃到老鼠的期望步数。这个东西可以用记忆化搜索轻松解决。

#include <bits/stdc++.h>
using namespace std;
const int maxm=3002;
const int maxn=1002;
typedef double db;
int to[maxm],nxt[maxm],head[maxn],num;
void add(int x,int y){num++;to[num]=y;nxt[num]=head[x];head[x]=num;}
int n,m;
int cat,mou;
int d[maxn][maxn];int deg[maxn];db f[maxn][maxn];
int dis[maxn][maxn],vis[maxn];
void spfa(int S)
{
	for(int i=1;i<=n;i++) 
		vis[i]=0;
	queue<int> Q;
	dis[S][S]=0; Q.push(S); vis[S]=1;
	while(!Q.empty())
	{
		int p=Q.front(); vis[p]=0; Q.pop();
		for(int i=head[p];i;i=nxt[i])
		{
			if(dis[S][to[i]]>dis[S][p]+1)
			{
				dis[S][to[i]]=dis[S][p]+1;
				if(!vis[to[i]]) vis[to[i]]=1,Q.push(to[i]);
			}
		}
	}	
}
void pre()
{
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++)
		spfa(i);
	for (int i=1;i<=n;i++)
	{
		for (int h=head[i];h;h=nxt[h])
		{
			int t=to[h];
			for (int j=1;j<=n;j++)
				if(dis[i][j]-1==dis[t][j])
					d[i][j]=min(d[i][j],t);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			f[i][j]=-1;
	}
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			fprintf(stderr,"%d %d : %d\n",i,j,d[i][j]);
	}*/
}
db solve(int x,int y)
{
	if(f[x][y]>=0) return f[x][y];
	if(x==y) return f[x][y]=0;
	if(dis[x][y]<=2) return f[x][y]=1;
	db ret=1;int sec=d[d[x][y]][y];
	ret+=solve(sec,y)/(deg[y]+1);
	for(int i=head[y];i;i=nxt[i])
	{
		int v=to[i];
		ret+=solve(sec,v)/(deg[y]+1);
	}
	return f[x][y]=ret;
}
int main()
{
	//freopen("p.in","r",stdin);
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d",&n,&m);
	scanf("%d%d",&cat,&mou);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
		deg[x]++;deg[y]++;
	}
	pre();
	printf("%.3lf",solve(cat,mou));
}