前言：学长讲的太神了；自己还能推出来DP式子，挺开心。
--------------------------
题目大意：给定一张含有$n$个结点$m$条边的无向连通图。现在聪聪在点$s$，可可在点$t$。每秒钟可可能等概率走向相邻的结点或原地不动，而聪聪总是向更靠近可可的地方沿最短路走两步（如果走一步就能找到可可就不往下走了）。问聪聪找到可可的时间的期望。$n,mleq 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[1005][1005],next[1005][1005],du[1005],vis[1005]; int n,m,s,t,visit[1005][1005]; double f[1005][1005]; int head[2005],cnt; struct node { int next,to,dis; }edge[2005]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';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]=0;vis[x]=1;q.push(x); while(!q.empty()) { int now=q.front();q.pop();vis[now]=0; 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]=1; } } } } double dfs(int u,int v) { if (visit[u][v]) return f[u][v]; if (u==v) return 0; int fir=next[u][v]; int sec=next[fir][v]; if (fir==v||sec==v) return 1; f[u][v]=1; for (int i=head[v];i;i=edge[i].next) { int to=edge[i].to; f[u][v]+=dfs(sec,to)/(double)(du[v]+1); } f[u][v]+=dfs(sec,v)/(double)(du[v]+1); visit[u][v]=1; return f[u][v]; } int main() { n=read(),m=read(),s=read(),t=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(); add(x,y,1); add(y,x,1); du[x]++,du[y]++; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=next[i][j]=0x3f3f3f3f; for (int i=1;i<=n;i++) spfa(i); for (int i=1;i<=n;i++) for (int j=head[i];j;j=edge[j].next) { int to=edge[j].to; for (int k=1;k<=n;k++) if (dis[i][k]-1==dis[to][k]) next[i][k]=min(next[i][k],to); } printf("%.3lf",dfs(s,t)); return 0; }