NOI2005 聪聪与可可

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

聪聪与可可

题面

在一个魔法森林里，住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽然灰姑娘非常喜欢她们俩，但是，聪聪终究是一只猫，而可可终究是一只老鼠，同样不变的是，聪聪成天想着要吃掉可可。

一天，聪聪意外得到了一台非常有用的机器，据说是叫 $GPS$，对可可能准确的定位。有了这台机器，聪聪要吃可可就易如反掌了。于是，聪聪准备马上出发，去找可可。而可怜的可可还不知道大难即将临头，仍在森林里无忧无虑的玩耍。小兔子乖乖听到这件事，马上向灰姑娘报告。灰姑娘决定尽快阻止聪聪，拯救可可，可她不知道还有没有足够的时间。

整个森林可以认为是一个无向图，图中有 $N$ 个美丽的景点，景点从 $1$ 至 $N$ 编号。小动物们都只在景点休息、玩耍。在景点之间有一些路连接。

当聪聪得到 $GPS$ 时，可可正在景点 $M$($M\le N$)处。以后的每个时间单位，可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻，它们分别是景点 R、景点 S，……景点 Q，在时刻 $T$ 可可处在景点 M，则在( $T+1$ )时刻，可可有 $\frac 1{1+p}$ 的可能在景点 R，有 $\frac 1{1+p}$ 的可能在景点 S，……，有 $\frac 1{1+p}$ 的可能在景点 Q，还有$\frac 1{1+p}$ 的可能停在景点 M。

我们知道，聪聪是很聪明的，所以，当她在景点 C 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。由于聪聪太想吃掉可可了，如果走完第一步以后仍然没吃到可可，她还可以在本段时间内再向可可走近一步。

在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可怜的可可就被吃掉了。

灰姑娘想知道，平均情况下，聪聪几步就可能吃到可可。而你需要帮助灰姑娘尽快的找到答案。

Input

数据的第 $1$ 行为两个整数 $N$ 和 $E$，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。

第 $2$ 行包含两个整数 $C$ 和 $M$，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。

接下来 $E$ 行，每行两个整数，第 $i+2$ 行的两个整数 $A_i$和$B_i$ 表示景点 $A_i$和景点 $B_i$ 之间有一条路。所有的路都是无向的，即：如果能从 $A$ 走到 $B$，就可以从 $B$ 走到 $A$。

输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output

输出 $1$ 个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Sample Input 1

4 3
1 4
1 2
2 3
3 4

Sample Output 1

1.500

Sample Input 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 2

2.167

Hint

对于 $50\%$ 的数据，$1≤N≤50$。

对于所有的数据，$1\le N,E\le 1000$。

题目是说，聪聪能走一步或两步，可可能不动；聪聪一定会走离可可最近的点中编号最小的点。

预处理：

预处理出每个点之间的最短路径$Dis$。
枚举聪聪和可可各在$i、j$的情况，聪聪下一步会走到的点$NextStep$。

设$dp_{i,j}$表示聪聪在$i$，可可在$j$时，聪聪抓到可可的概率。

我们很容易的分类推出：

聪聪可可在一个点上时 → $dp_{i,j}=0$
聪聪可以在一次行动后就能够抓到可可 → $dp_{i,j}=1$
非以上情况，则猫肯定要走两步以上，那么走两步的结果肯定优于只走一步，设聪聪在走$2$步之后会走到$k$，可可能够到达$l$ → $dp_{i,j}=\frac 1{p_j+1}\sum dp_{k,l}+1$

通过记搜来优化即可。

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
const int N=1010;
struct edge{
	int to,nxt;
}e[N<<1];
int linkk[N<<1],len;
int n,E,c,m;
void insert(int u,int v)
{
	e[++len].to=v,e[len].nxt=linkk[u],linkk[u]=len;
	e[++len].to=u,e[len].nxt=linkk[v],linkk[v]=len;
}
int dis[N][N],nextstep[N][N];
bool flag[N][N],vis[N];
double dp[N][N];
int p[N];
queue<int> q;
void spfa(int i)
{
	memset(vis,0,sizeof(vis));
	dis[i][i]=0;
	q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int j=linkk[x];j;j=e[j].nxt)
		{
			int to=e[j].to;
			if(dis[i][x]+1<dis[i][to])
			{
				dis[i][to]=dis[i][x]+1;
				if(vis[to]) continue;
				vis[to]=1;
				q.push(to);
			}
		}
	}
}
bool visi[N][N];
double DP(int u,int v)
{
	// cerr<<"TET"<<endl;
	if(visi[u][v]) return dp[u][v];
	if(u==v) return 0;
	int p1=nextstep[u][v],p2=nextstep[p1][v];
	if(p1==v||p2==v) return 1;
	dp[u][v]=1;
	for(int i=linkk[v];i;i=e[i].nxt)
	{
		int to=e[i].to;
		dp[u][v]+=DP(p2,to)/(p[v]+1);
	}
	dp[u][v]+=DP(p2,v)/(p[v]+1);
	visi[u][v]=1;
	return dp[u][v];
}
int main(int argc, char const *argv[])
{
	n=read(),E=read(),c=read(),m=read();
	for(int i=1;i<=E;++i)
	{
		int a=read(),b=read();
		insert(a,b);
		++p[a],++p[b];
	}
	memset(dis,0x7f,sizeof(dis));
	memset(nextstep,0x7f,sizeof(nextstep));
	for(int i=1;i<=n;++i) spfa(i);
	for(int i=1;i<=n;++i)
	{
		for(int j=linkk[i];j;j=e[j].nxt)
		{
			int to=e[j].to;
			for(int k=1;k<=n;++k)
				if(dis[i][k]-1==dis[to][k])
					nextstep[i][k]=min(nextstep[i][k],to);
		}
	}
	printf("%.3lf\n",DP(c,m));
	return 0;
}