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);
}