Description#

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

题解#

先每个点跑一遍SPFA
求出p[i][j]表示当可可在 j 点时，聪聪在 i 点要走的下一步
然后记忆化搜索
$f[s][e]=\sum_{tmp=p[p[i][e]][e],e->j}{\frac{f[tmp][j]}{du[e]+1}}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct edge{
    int END,next;
}v[100005];
int first[1005],Index,du[1005],n;
void add(int a,int b){
    du[a]++;
    v[Index].END=b;
    v[Index].next=first[a];
    first[a]=Index++;
}
int p[1005][1005];
double f[1005][1005];
void spfa(int x){
    queue<int> Q;
    bool flag[1005]={0};
    int dis[1005],fr[1005];
    memset(dis,0x3f,sizeof(dis));
    memset(fr,0,sizeof(fr));
    dis[x]=0;
    flag[x]=1;Q.push(x);
    while(!Q.empty()){
        int k=Q.front();
        Q.pop();flag[k]=0;
        for(int i=first[k];i!=-1;i=v[i].next){
            if(dis[v[i].END]>dis[k]+1||(dis[v[i].END]==dis[k]+1&&k<fr[v[i].END])){
                dis[v[i].END]=dis[k]+1;
                fr[v[i].END]=k;
                if(!flag[v[i].END]){
                    flag[v[i].END]=1;
                    Q.push(v[i].END);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(i!=x)
            p[i][x]=fr[i];
}
double dfs(int s,int e){
    if(s==e)return f[s][e]=0;
    if(p[s][e]==e||p[p[s][e]][e]==e)return f[s][e]=1;
    if(f[s][e]<=1e9) return f[s][e];
    int tmp=p[p[s][e]][e];
    f[s][e]=1;
    for(int i=first[e];i!=-1;i=v[i].next){
        f[s][e]+=dfs(tmp,v[i].END)/(du[e]+1);
    }
    f[s][e]+=dfs(tmp,e)/(du[e]+1);
    return f[s][e];
}
int main()
{
    //freopen("cchkk.in","r",stdin);
	//freopen("cchkk.out","w",stdout);
    memset(first,-1,sizeof(first));
    memset(f,0x7f,sizeof(f));
    int m,s,e,a,b;
    scanf("%d%d%d%d",&n,&m,&s,&e);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)
        spfa(i);
    printf("%.3lf",dfs(s,e));
    //while(1);
}