Input
数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。 接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。
Output
输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。
Sample Input
【输入样例1】

4 3

1 4

1 2

2 3

3 4

【输入样例2】

9 9

9 3

1 2

2 3

3 4

4 5

3 6

4 6

4 7

7 8

8 9

Sample Output
【输出样例1】

1.500

【输出样例2】

2.167

PoPo大爷写了非常详解的题解，http://blog.csdn.net/PoPoQQQ/article/details/40896403 对蒟蒻来说这个题的信

息量还是很大的，但实际上又很水，这就是信息学的魅力吧。

首先我们知道，由于聪聪走两步而可可走一步，所以聪聪一定能在有限的时刻追上可可，而且两人的距离随着时间进行

单调递减

于是我们记忆化搜索

首先用预处理出一个数组p[i][j]，表示当聪聪在点i，可可在点j时聪聪下一步走哪个点 这个从每个点出发跑一遍SPFA就

可以处理出来

然后就可以记忆化搜索了 令f[i][j]为当聪聪在点i，可可在点j时的期望相遇时

若i==j 则f[i][j]=0

若p[i][j]==j||p[p[i][j]][j]==j则f[i][j]=1

否则令temp=p[p[i][j]][j]，则有

我为了不统计度数，直接加了一条自己到自己的边，然后直接BFS，懒得spfa了。

//BZOJ 1415

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int inf=0x3f3f3f3f;
struct edge{
    int v, nxt;
    edge(){}
    edge(int v,int nxt):v(v), nxt(nxt){}
}E[maxn*5];

int head[maxn], edgecnt;
void init(){
    edgecnt = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v){
    E[edgecnt].v=v,E[edgecnt].nxt=head[u],head[u]=edgecnt++;
}
int dist[maxn][maxn], p[maxn][maxn];
///p[i][j]聪聪在i点可可在j点，聪聪下一步走哪个点
int n, m, s, t;
double f[maxn][maxn];
bool vis[maxn][maxn];

double dfs(int x, int y)
{
    if(vis[x][y]) return f[x][y];
    vis[x][y]=1;
    if(dist[x][y]==0) return f[x][y]=0.0;
    if(dist[x][y]<=2) return f[x][y]=1.0;
    double val = 0;
    int cnt=0;
    for(int i=head[y];~i;i=E[i].nxt){
        cnt++;
        val+=dfs(p[p[x][y]][y],E[i].v);
    }
    return f[x][y]=val/cnt+1.0;
}

queue <int> que;
void bfs(int s)
{
    que.push(s);
    dist[s][s]=0;
    while(!que.empty()){
        int u=que.front(); que.pop();
        for(int i=head[u];~i;i=E[i].nxt){
            int v=E[i].v;
            if(dist[s][v]==-1){
                dist[s][v]=dist[s][u]+1;
                que.push(v);
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d", &n,&m,&s,&t);
    init();
    while(m--){
        int a,b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    memset(dist, -1, sizeof(dist));
    for(int k=1; k<=n; k++){
        bfs(k);
        for(int j=1; j<=n; j++){
            if(j!=k){
                int mx = inf;
                for(int i=head[j];~i;i=E[i].nxt){
                    if(mx>dist[k][E[i].v]){
                        mx = dist[k][E[i].v];
                        p[j][k]=E[i].v;
                    }
                    else if(mx==dist[k][E[i].v]){
                        p[j][k]=min(p[j][k],E[i].v);
                    }
                }
            }
        }
    }
    for(int i=1; i<=n; i++) add(i,i);
    printf("%.3lf\n", dfs(s, t));
    return 0;
}