输入格式：

数据的第 1 行为两个整数 N 和 E，以空格分隔，分别表示森林中的景点数和 连接相邻景点的路的条数。

第 2 行包含两个整数 C 和 M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。

接下来 E 行，每行两个整数，第 i+2i+2 行的两个整数 Ai​和 Bi​表示景点 Ai​和景点 Bi​ 之间有一条路。 所有的路都是无向的，即：如果能从 A 走到 B，就可以从 B 走到 A。

输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

输出格式：

输出 1 个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

对于 50%的数据，1≤N≤50。

对于所有的数据，1≤N,E≤1000。

题解

 当聪聪和可可位置一定，那么聪聪的走法是一定的；

每个单位时间，聪聪最多走两步，可可走一步，所以一定是越来越近的，那么dfs来dp就一定可以得到答案。

先于处理出当聪聪在i位置可可在j位置时，聪聪下一步的走法go[i][j]

实现方法是先用Dijkstra求出每两点之间的最短距离，再枚举点，若dis[i][j]==dis[y][j]+1,那么y就可能是这条路径上i的下一个点，去min即可

由于n很小，所以不会T

在dfs时要除以（du[kk]+1），因为可可可以不动

#include
      
       using namespace std;const int maxn=1005;int n,m;int S,T;//聪聪，可可 int du[maxn];int go[maxn][maxn];//i到j的最短路,i的下一步 double f[maxn][maxn];int cnt,head[maxn];struct edge{    int y,next;}e[maxn<<1];int min(int x,int y){
    return x
       
        ,vector
        
         
           >,greater
          
           
             > > q; q.push(make_pair(0,s)); dis[s][s]=0; while(!q.empty()){ int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=true; for(int i=head[x];i;i=e[i].next){ int y=e[i].y; if(dis[s][y]>dis[s][x]+1){ dis[s][y]=dis[s][x]+1; q.push(make_pair(dis[s][y],y)); } } }}double dfs(int cc,int kk){ if(cc==kk) return 0.0; if(go[cc][kk]==kk) return 1.0; if(go[go[cc][kk]][kk]==kk) return 1.0; if(f[cc][kk]!=-1.0) return f[cc][kk]; double ret=0; for(int i=head[kk];i;i=e[i].next){ int y=e[i].y; ret+=(dfs(go[go[cc][kk]][kk],y)+1.0)/(du[kk]+1); } ret+=(dfs(go[go[cc][kk]][kk],kk)+1.0)/(du[kk]+1); return f[cc][kk]=ret;}int main(){ memset(dis,0x3f,sizeof(dis)); scanf("%d%d",&n,&m); scanf("%d%d",&S,&T); memset(go,0x3f,sizeof(go)); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); du[x]++;du[y]++; add(x,y);add(y,x); } for(int i=1;i<=n;i++) ds(i);// for(int i=1;i<=n;i++,putchar(10))// for(int j=1;j<=n;j++)// printf("%d ",dis[i][j]); for(int i=1;i<=n;i++) for(int k=head[i];k;k=e[k].next){ int y=e[k].y; for(int j=1;j<=n;j++) if(dis[i][j]==dis[y][j]+1) go[i][j]=min(go[i][j],y); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=-1.0; printf("%.3lf",dfs(S,T));}