http://vjudge.net/problem/viewProblem.action?id=20613
题意：不用说了，中文题。
这个题可以用概率DP来做。
题中要求猫抓到老鼠的时间期望。分析一下这个过程，如果猫在每单位时间里第一步移动没有抓到老鼠，它还可以继续移动一次。对于确定老鼠的位置，注意猫的每次移动都是固定的，而老鼠的移动位置却是不定的。
令dp[i][j]表示猫在i位置老鼠在j位置时，猫抓到老鼠的期望。next[i][j]表示猫从i位置到j位置时走最短路径需要移动到的第一个结点位置。d[i]表示结点i的度。
这样首先看猫的当前位置，如果i==j即猫和老鼠在同一个点，那么猫不用移动了这时候猫已经抓到了老师，dp[i][j]=0。
如果不等，考虑如果猫在这两次移动中抓到了老鼠，如果猫第一步移动到了老鼠当前所在位置，即next[i][j]==j,或者猫第二步移动抓到了老鼠，即next[next[i][j]][j]==j,此时所用时间都是1，dp[i][j]=1。
其他情况，考虑猫在该单位时间内没抓到老鼠，此时的状态转移取决于老鼠的行动。老鼠可以移动到任意一个和j结点相连的点，也可以停留在j点，每种情况发生的概率是1/(d[j]+1),每次转移到的状态即dp[next[next[i][j]][j]][k](k取值j,或与j点直接连边的点），运用全期望公式即可。
这样记忆化搜索可解。
其中计算next[][]的过程可以用bfs预处理。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
#define MAXN 30005
using namespace std;
int n,m;
vector<];
][];
][];
][];
struct Point
{
int pos,from;
Point(,):pos(a),from(b) {}
};
void bfs(int sst)
{
]= {};
queue<Point> que;
que.push(Point(sst));
while(!que.empty())
{
Point q=que.front();
que.pop();
; i<gl[q.pos].size(); ++i)
{
if(vis[gl[q.pos][i]]) continue;
vis[gl[q.pos][i]]=true;
int f;
if(q.pos==sst) f=gl[q.pos][i];
else f=q.from;
que.push(Point(gl[q.pos][i],f));
next[sst][gl[q.pos][i]]=f;
}
}
}
double dp(int i,int j)
{
if(vis[i][j]) return f[i][j];
vis[i][j]=true;
int &p=next[i][j];
;
;
f[i][j]=;
; k<gl[j].size(); ++k)
f[i][j]+=dp(next[p][j],gl[j][k]);
f[i][j]+=dp(next[p][j],j);
f[i][j]/=(gl[j].size()+);
f[i][j]++;
return f[i][j];
}
int main()
{
scanf("%d%d",&n,&m);
int st,ed;
scanf("%d%d",&st,&ed);
; i<m; ++i)
{
int x,y;
scanf("%d%d",&x,&y);
gl[x].push_back(y);
gl[y].push_back(x);
}
; i<=n; ++i)
{
sort(gl[i].begin(),gl[i].end());
bfs(i);
}
memset(vis,,sizeof(vis));
printf("%.3lf\n",dp(st,ed));
;
}