[BZOJ1415][NOI2005]聪聪与可可

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

HINT

【样例说明1】
开始时，聪聪和可可分别在景点1和景点4。
第一个时刻，聪聪先走，她向更靠近可可(景点4)的景点走动，走到景点2，然后走到景点3；假定忽略走路所花时间。
可可后走，有两种可能：
第一种是走到景点3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为1，概率为。
第二种是停在景点4，不被吃掉。概率为。
到第二个时刻，聪聪向更靠近可可(景点4)的景点走动，只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1* +2* =1.5步。

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

怎么办啊我太菜了这么简单的题都想不到...

首先用spfa预处理出nxt数组。

nxt[i, j]表示聪聪在i，可可在j，聪聪的下一步调到哪里。

我们对于每个点x都bfs一次，算出所有点到达它的最短路。

然后枚举点y，把x当做可可，y当做聪聪，然后枚举y的所有出边，这些边所到达的点是聪聪可以跳到的。

所以就记录一下最小的dis，如果有更小的dis就更新nxt[y, x]，如果有相同的dis，nxt[y, x]就和to取min...

这样处理出来nxt数组后，我们就可以毫无压力的进行dp；

设f[i, j]表示聪聪在i，可可在j，聪聪要吃掉可可的期望步数。

然后推一波公式...

$LARGE f[i, j]=frac{sum_{to}^{ } f[nxt[nxt[i,j],j],to] + f[nxt[nxt[i,j],j],j]}{deg[j]+1} + 1$

然后如果聪聪可可在一个点上那么直接是0，如果nxt[nxt[i,j],j] = j 或者 nxt[i,j]=j那么直接f[i,j]=1；

这个可以用记忆化搜索实现...

我还是太菜了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define gc getchar()
inline int read(){
    int res=0;char ch=gc;
    while(!isdigit(ch))ch=gc;
    while(isdigit(ch)){res=(res<<3)+(res<<1)+(ch^48);ch=gc;}
    return res;
}
#undef gc

int n, m, c, e;
int nxt[1005][1005], dis[1005], deg[1005];
double f[1005][1005];
struct edge{
    int nxt, to;
}ed[2005];
int head[1005], cnt;
inline void add(int x, int y)
{
    ed[++cnt] = (edge){head[x], y};
    head[x] = cnt;
}

bool ex[1005];
inline void bfs(int cur)
{
    memset(dis, 0x3f, sizeof dis);
    memset(ex, 0, sizeof ex);
    dis[cur] = 0;
    queue <int> q;
    q.push(cur);
    while(!q.empty())
    {
        int x = q.front();q.pop();
        ex[x] = 0;
        int tmp = nxt[cur][x];
        for (int i = head[x] ; i ; i = ed[i].nxt)
        {
            int to = ed[i].to;
            if (dis[to] > dis[x] + 1 )
            {
                dis[to] = dis[x] + 1;
                if (!ex[to]) ex[to] = 1, q.push(to);
            }
        }
    }
    for (int x = 1 ; x <= n ; x ++)
    {
        if (x == cur) continue;
        int mn = 1e9;
        for (int i = head[x] ; i ; i = ed[i].nxt)
        {
            int to = ed[i].to;
            if (dis[to] < mn) mn = dis[to], nxt[x][cur] = to;
            else if (dis[to] == mn) if (nxt[x][cur] > to) nxt[x][cur] = to;
        }
    }
}

double dp(int x, int y) //猫的位置x，鼠的位置y 
{
    if (f[x][y]) return f[x][y];
    if (x == y) return 0;
    if (nxt[nxt[x][y]][y] == y or nxt[x][y] == y) return f[x][y] = 1;
    double sum = 0;
    for (int i = head[y] ; i ; i = ed[i].nxt)
    {
        int to = ed[i].to;
        sum += dp(nxt[nxt[x][y]][y], to);
    }
    sum += dp(nxt[nxt[x][y]][y], y);
    return f[x][y] = sum / (deg[y] + 1) + 1.0;
}

int main()
{
    n = read(), m = read(), c = read(), e = read();
    
    for (int i = 1 ; i <= m ; i ++) 
    {
        int x = read(), y = read();
        add(x, y), add(y, x);
        deg[x]++, deg[y]++;
    }
    
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1 ; i <= n ; i ++) bfs(i);
    printf("%.3lf
", dp(c, e));
    return 0;
}