首先预处理出可可在点s ，聪聪在点i 时，聪聪的下一步
对每个s 做一遍单源最短路，枚举所有点i 的出边，选择其中距离较短且序号较小的点作为下一步
设为聪聪在点u 可可在点v 的期望步数
- u=v ，
- 当前回合能抓到，
- 其他情况
设x 为聪聪下一步
记忆优化搜索即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
const int N=1050,INF=1<<30;
int st,ed,n,m,nxt[N][N],f[N][N];
int inq[N],d[N];
double dp[N][N];
vector<int> e[N];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void SPFA(int s)
{
for(int i=1;i<=n;i++) d[i]=INF;
d[s]=0,inq[s]=1,Q.push(s);
while (!Q.empty())
{
int x=Q.front();
inq[x]=0,Q.pop();
for(int i=0;i<e[x].size();i++)
{
int to=e[x][i];
if (d[x]+1<d[to])
{
d[to]=d[x]+1;
if (!inq[to]) Q.push(to),inq[to]=1;
}
}
}
for(int i=1;i<=n;i++) if (i!=s)
for(int j=0;j<e[i].size();j++)
{
int to=e[i][j];
if (!nxt[i][s]||d[to]<d[nxt[i][s]]) nxt[i][s]=to;
if (d[to]==d[nxt[i][s]]&&to<nxt[i][s]) nxt[i][s]=to;
}
}
double dfs(int u,int v)
{
if (f[u][v]) return dp[u][v];
if (u==v) return 0;
if (nxt[u][v]==v) return 1;
int x=nxt[nxt[u][v]][v];
if (x==v) return 1;
for(int i=0;i<e[v].size();i++)
{
int to=e[v][i];
dp[u][v]+=dfs(x,to)/(1+e[v].size());
}
dp[u][v]+=dfs(x,v)/(1+e[v].size())+1;
f[u][v]=1;
return dp[u][v];
}
int main()
{
n=read(),m=read();
st=read(),ed=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++) SPFA(i);
printf("%.3lf\n",dfs(st,ed));
return 0;
}