题目描述
输入
数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。 接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。
输出
输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。
样例输入
【输入样例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
样例输出
【输出样例1】
1.500
【输出样例2】
2.167
题解
期望记忆化搜索
先预处理出两个点之间的最短路，以及从那个点走来。
然后就是很水的期望dp。
设$f[i][j]$表示聪聪在$i$，可可在$j$时还要走的期望时间。
那么显然考虑$i$走两步到达的点$t$，$f[i][j]=\frac{\sum\limits_{dis[j][k]\le 1}f[t][k]}{d[j]+1}$。
由于两人距离一定是越来越小的，所以这个dp实际上是有序的（按照两点距离从小到大）。为了不特殊处理顺序，使用记忆化搜索就好了。
#include <queue>
#include <cstdio>
#include <algorithm>
#define N 1010
using namespace std;
queue<int> q;
int d[N] , head[N] , to[N << 1] , next[N << 1] , cnt , last[N][N] , dis[N][N];
double f[N][N];
void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt , d[x] ++ ;
}
void bfs(int u)
{
int x , i;
last[u][u] = -1 , q.push(u);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
if(!last[u][to[i]]) last[u][to[i]] = x , dis[u][to[i]] = dis[u][x] + 1 , q.push(to[i]);
else if(dis[u][to[i]] == dis[u][x] + 1 && last[u][to[i]] > x) last[u][to[i]] = x;
}
}
}
double dfs(int x , int y)
{
if(dis[x][y] == 0) return 0;
if(f[x][y] > 0) return f[x][y];
if(dis[x][y] <= 2) return f[x][y] = 1;
int t = last[y][last[y][x]] , i;
double ret = dfs(t , y) / (d[y] + 1);
for(i = head[y] ; i ; i = next[i]) ret += dfs(t , to[i]) / (d[y] + 1);
return f[x][y] = ret + 1;
}
int main()
{
int n , m , p1 , p2 , x , y , i;
scanf("%d%d%d%d" , &n , &m , &p1 , &p2);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
for(i = 1 ; i <= n ; i ++ ) bfs(i);
printf("%.3lf\n" , dfs(p1 , p2));
return 0;
}