题意：给一张无向图，有一只猫和一只老鼠，猫每秒会向老鼠的方向移动两个单位，若它们的距离为一，那么只会移动一个单位，老鼠会等概率向周围移动一步或不动，求猫抓到老鼠的期望时间。
SolutionluoguAC第800题。
注意到猫的运动之和猫的位置和老鼠的位置有关，我们可以对其进行预处理，注意若有多种方案的情况会向编号小的点移动。
然后发现猫和老鼠的距离一定是会减小的，不如记录状态进行记忆化搜索，这样转移是不会出现环的。
Code
#include#include #include #include #define N 1002using namespace std;queue q;const double eps=1e-10;int head[N],dis[N][N],tot,tag[N][N],n,m,s,t;bool vis[N];double dp[N][N];struct zzh{ int n,to;}e[N<<1];inline void add(int u,int v){ e[++tot].n=head[u]; e[tot].to=v; head[u]=tot;}double dfs(int s,int t){ if(dp[s][t]>eps)return dp[s][t]; if(s==t)return 0; int ss=tag[s][t]; if(ss==t)return 1; ss=tag[ss][t]; if(ss==t)return 1; double sum=0,ans=0; for(int i=head[t];i;i=e[i].n)ans+=dfs(ss,e[i].to),sum++; ans+=dfs(ss,t);ans=ans/(sum+1)+1; return dp[s][t]=ans;}int main(){ scanf("%d%d%d%d",&n,&m,&s,&t);int u,v; for(int i=1;i<=m;++i){scanf("%d%d",&u,&v);add(u,v);add(v,u);} memset(dis,0x3f,sizeof(dis));memset(tag,0x3f,sizeof(tag)); for(int i=1;i<=n;++i){ dis[i][i]=0; q.push(i); while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int j=head[u];j;j=e[j].n){ int v=e[j].to; if(dis[i][v]>dis[i][u]+1){ dis[i][v]=dis[i][u]+1; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } for(int i=1;i<=n;++i) for(int k=1;k<=n;++k) for(int j=head[i];j;j=e[j].n) if(dis[i][k]==dis[i][e[j].to]+dis[e[j].to][k])tag[i][k]=min(e[j].to,tag[i][k]); printf("%.3lf",dfs(s,t)); return 0;}