期望DP+记搜
聪聪一直在向可可方向追，所以不会回到原处，不具有后效性，考虑用概率与期望DP+记忆化搜索求解
用dp[x][y]表示可可在x点,聪聪在y点时步数的期望值
判断边界
①当x==y时结束 （此时毫无疑问的，dp[x][y]=0）
②当x!=y时 若x与y的距离等于1或2时则dp[x][y]=1
（原因：若x距离y只有一步，则dp[x][y]=1;若x距离y两步，因为x也可一次移动两步，两者依旧可以通过一次重合，dp[x][y]=1）
预处理
对图中每个x，到y的最短距离（BFS求单源最短路径 O（n^2），不会的也可以BDFS自行学习广搜），将当前y的下一个位置预处理为nex(x,y)
推导
根据期望的定义得到递推式dp[x]=∑1/(p+1)*dp[x’][nex(x,nex(x,y))]
（1/(p+1)为到达每一个新状态的概率，然后就根据两步之内可能的状态进行递推，对其进行求和，即为当前的期望步数）
AT LAST 状态转移
1.dp[x][y]=0 (x==y)
2.dp[x][y]=1(1<=dis(x,y)<=2)
3.dp[x][y]=∑1/(p+1)*dp[x’][nex(x,nex(x,y))]
然后就应该结束贴代码了
然而并没有
对于记忆化搜索的每一步，假设nex[x][y]y或nex[nex[x][y]][y]y，那么只差一步就能到。可可每一步的行动可能是不动也可能走到相邻节点，可能性即为y的度数+1.
AC代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1010;
const double inf=-1.0;
int tot;
double ans;
int n,e_num,c,m;
int ind[maxn];
int head[maxn];
int dis[maxn][maxn];
int nex[maxn][maxn];
double dp[maxn][maxn];
struct node
{
int to;
int next;
}e[2*maxn];
void add(int x,int y)
{
tot++;
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
void BFS(int x)
{
queue <int> q;
q.push(x);
dis[x][x]=0;
while(!q.empty())
{
int from=q.front();
q.pop();
for(int i=head[from];i;i=e[i].next)
{
int to=e[i].to;
if(dis[x][to]==-1)
{
dis[x][to]=dis[x][from]+1;
q.push(to);
}
}
}
}
double DFS(int x,int y)
{
if(dp[x][y]!=-1.0)
{
return dp[x][y];
}
if(x==y)
{
return dp[x][y]=0;
}
if(nex[x][y]==y || nex[nex[x][y]][y]==y)
{
return dp[x][y]=1.0;
}
dp[x][y]=0.0;
for(int i=head[y];i;i=e[i].next)
{
dp[x][y]+=DFS(nex[nex[x][y]][y],e[i].to);
}
dp[x][y]=(dp[x][y]+DFS(nex[nex[x][y]][y],y))/(double)(ind[y]+1)+1;
return dp[x][y];
}
int main()
{
cin>>n>>e_num;
cin>>c>>m;
for(int i=1;i<=e_num;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
ind[x]++;
ind[y]++;
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
dp[i][j]=-1.0;
}
}
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;i++)
{
BFS(i);
}
memset(nex,0x3f3f3f,sizeof(nex));
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=e[j].next)
{
int to=e[j].to;
for(int k=1;k<=n;k++)
{
if(dis[i][k]==dis[to][k]+1 && nex[i][k]>to)
{
nex[i][k]=to;
}
}
}
}
ans=DFS(c,m);
printf("%.3lf",ans);
return 0;
}