【题意】给定无向图，聪聪和可可各自位于一点，可可每单位时间随机向周围走一步或停留，聪聪每单位时间追两步（先走），问追到可可的期望时间。n<=1000。
【算法】期望DP+记忆化搜索
【题解】首先因为聪聪的步数大于可可，所以不可能出现循环，因此是DAG上的期望DP，用记忆化搜索解决。
每个点bfs预处理p[x][y]表示x走向y的第一步位置，设f[x][y]表示聪聪在x可可在y追上的期望时间。
$$f(x,y)=\sum_{z}\frac{f(g[g[i][j]]][j],z)}{out[x]+1}+1$$
其中z是y的邻点和y自身。
再判断一下一步到达，两步到达和重叠（可可随机到聪聪处）的情况即可。
复杂度O(n^2)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
struct edge{int from,v;}e[maxn*];
int n,m,a,b,ins[maxn],first[maxn],d[maxn],q[],p[maxn][maxn],tot;
double f[maxn][maxn];
void insert(int u,int v)
{
tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;ins[u]++;
tot++;e[tot].v=u;e[tot].from=first[v];first[v]=tot;ins[v]++;
}
double dp(int a,int b)
{
if(f[a][b])return f[a][b];
if(a==b)return f[a][b]=;
if(p[a][b]==b||p[p[a][b]][b]==b)return f[a][b]=;
double ans=dp(p[p[a][b]][b],b);
for(int i=first[b];i;i=e[i].from)
ans+=dp(p[p[a][b]][b],e[i].v);
return f[a][b]=ans/(1.0*ins[b]+)+;
}
void bfs(int x)
{
memset(d,-,sizeof(d));
int head=,tail=;d[x]=;p[x][x]=;
for(int i=first[x];i;i=e[i].from)p[x][e[i].v]=e[i].v,d[e[i].v]=,q[tail++]=e[i].v;
while(head!=tail)
{
int y=q[head++];if(head>)head=;int num=p[x][y];
for(int i=first[y];i;i=e[i].from)
if(d[e[i].v]==-||((d[y]+==d[e[i].v])&&num<p[x][e[i].v]))
{
d[e[i].v]=d[y]+;
p[x][e[i].v]=num;
q[tail++]=e[i].v;
if(tail>)tail=;
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
}
for(int i=;i<=n;i++)bfs(i);
printf("%.3lf",dp(a,b));
return ;
}