[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=57148470
Descrition 
首先很明显是期望dp。但是如何进行转移呢？
对于dp，什么样的状态容易储存呢？怎样又分解成相应的子问题呢？于是发现，对于这个问题，我们需要知道猫的位置到老鼠位置的期望值。与这样的相似的状态有很多。观察数据范围，是可以用二维数组存下的。所以我们用f[i][j]表示猫在i点，老鼠在j点的答案。
转移方程：
f[i][j]=sigma(f[i’][j’]*1/(degree[j]+1))+1
i’表示猫在i会移动到的下一个景点（因为是猫先动，所以i’可以直接算出来），j’表示j的后继状态们（老鼠可以到达的点和当前点）
然而对于这样的方程要怎么递推呢？死都没想出来。直到看了网上的题解才想起dp还有记忆化搜索的类型。
对于如何在已知猫和老鼠的位置，确定猫的下一步走法？用最短路就好了，顺带处理一下d[i][j]的值（表示猫在i老鼠在j的猫的下一步）。我比较喜欢用spfa
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000+5;
int n,e,st,ed;
int p[N][N],dis[N],deg[N];
double f[N][N];
bool exi[N];
int head[N],end[N*2],nxt[N*2],hh=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void adde(int a,int b){
hh++;
end[hh]=b;
nxt[hh]=head[a];
head[a]=hh;
}
void spfa(int x){
memset(dis,0x3f,sizeof(dis));
memset(exi,0,sizeof(exi));
while(!q.empty()) q.pop();
p[x][x]=x;
dis[x]=0;
for(int i=head[x];i;i=nxt[i]){
int v=end[i];
p[x][v]=v;
dis[v]=1;
q.push(make_pair(1,v));
exi[v]=1;
}
while(!q.empty()){
int u=q.top().second;q.pop();
exi[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=end[i];
if(dis[v]>=dis[u]+1){
if(dis[v]==dis[u]+1) p[x][v]=min(p[x][u],p[x][v]);
else p[x][v]=p[x][u];
dis[v]=dis[u]+1;
if(!exi[v]){
q.push(make_pair(dis[v],v));
exi[v]=1;
}
}
}
}
}
double dfs(int cat,int mice){
if(f[cat][mice]!=-1) return f[cat][mice];
if(p[p[cat][mice]][mice]==mice) return f[cat][mice]=1;
double ans=0;
int cc=p[p[cat][mice]][mice];
for(int i=head[mice];i;i=nxt[i]){
int v=end[i];
if(v==cc) continue;
ans+=dfs(cc,v)/(deg[mice]+1);
}
ans+=dfs(cc,mice)/(deg[mice]+1)+1;
return f[cat][mice]=ans;
}
int main(){
scanf("%d%d%d%d",&n,&e,&st,&ed);
int a,b;
for(int i=1;i<=e;i++){
scanf("%d%d",&a,&b);
adde(a,b),adde(b,a);
deg[a]++,deg[b]++;
}
for(int i=1;i<=n;i++) spfa(i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) f[i][j]=-1;
printf("%.3lf\n",dfs(st,ed));
return 0;
}