前言：学长讲的太神了；自己还能推出来DP式子，挺开心。
--------------------------
题目大意：给定一张含有$n$个结点$m$条边的无向连通图。现在聪聪在点$s$，可可在点$t$。每秒钟可可能等概率走向相邻的结点或原地不动，而聪聪总是向更靠近可可的地方沿最短路走两步（如果走一步就能找到可可就不往下走了）。问聪聪找到可可的时间的期望。$n,m\leq 1000$
----------------------
我们首先解决第一个限制条件：沿最短路走。
假设聪聪目前在点$i$，可可目前在点$j$，聪聪下一步的走位是$next[i][j]$。
看到数据范围，我们可以暴力把每个点的单源最短路径求出来，然后枚举距离点$i$距离为$1$的点$k$。如果$dis[i][j]-1==dis[k][j]$，那么$next[i][j]=k$。
然后进行期望DP。这里我们采用记忆化搜索。设$f[i][j]$表示目前聪聪在点$i$，可可在点$j$时的期望。设点的出度为$du[]$。然后分类讨论：
1.如果$i$和$j$同点，那么$f[i][j]=0$。
2.如果聪聪能够走一步或两步到达点$j$，那么$f[i][j]=1$。
3.如果可可呆在原地不动，那么对答案的贡献有$(f[next[next[i][j]][j]][j]+1)*\frac{1}{du[j]+1}$。（一共有$du[j]+1$种走法，包含原地不动）
4.如果可可走向相邻的点，那么对答案的贡献有$\sum (f[next[next[i][j]][j]][to]+1)*\frac{1}{du[j]+1}$。（枚举$to$）
所以总的DP方程为$f[i][j]=\frac{f[next[next[i][j]][j]][j]+\sum f[next[next[i][j]][j]][to]}{du[j]+1}+1$
最后输出$dfs(s,t)$即可。时间复杂度$O(n^2)$。
代码：
#include<bits/stdc++.h>
using namespace std;
int dis[][],next[][],du[],vis[];
int n,m,s,t,visit[][];
double f[][];
int head[],cnt;
struct node
{
int next,to,dis;
}edge[];
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}
while(isdigit(ch)){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void add(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
inline void spfa(int x)
{
queue<int> q;
dis[x][x]=;vis[x]=;q.push(x);
while(!q.empty())
{
int now=q.front();q.pop();vis[now]=;
for (int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if (dis[x][to]>dis[x][now]+edge[i].dis)
{
dis[x][to]=dis[x][now]+edge[i].dis;
if (!vis[to]) q.push(to),vis[to]=;
}
}
}
}
double dfs(int u,int v)
{
if (visit[u][v]) return f[u][v];
if (u==v) return ;
int fir=next[u][v];
int sec=next[fir][v];
if (fir==v||sec==v) return ;
f[u][v]=;
for (int i=head[v];i;i=edge[i].next)
{
int to=edge[i].to;
f[u][v]+=dfs(sec,to)/(double)(du[v]+);
}
f[u][v]+=dfs(sec,v)/(double)(du[v]+);
visit[u][v]=;
return f[u][v];
}
int main()
{
n=read(),m=read(),s=read(),t=read();
for (int i=;i<=m;i++)
{
int x=read(),y=read();
add(x,y,);
add(y,x,);
du[x]++,du[y]++;
}
for (int i=;i<=n;i++)
for (int j=;j<=n;j++) dis[i][j]=next[i][j]=0x3f3f3f3f;
for (int i=;i<=n;i++) spfa(i);
for (int i=;i<=n;i++)
for (int j=head[i];j;j=edge[j].next)
{
int to=edge[j].to;
for (int k=;k<=n;k++)
if (dis[i][k]-==dis[to][k]) next[i][k]=min(next[i][k],to);
}
printf("%.3lf",dfs(s,t));
return ;
}