记录编号	232494	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]聪聪与可可	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.343 s
提交时间	2016-03-01 18:11:52	内存使用	11.29 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=1000;
const double zero=1e-6;
int N,E;
deque<int> s[SIZEN];
int d[SIZEN]={0};
int C,M;
void read()
{
	scanf("%d%d",&N,&E);
	scanf("%d%d",&C,&M);
	int fr,to;
	for(int i=1;i<=E;i++) 
	{
		scanf("%d%d",&fr,&to);
		s[fr].push_back(to);
		s[to].push_back(fr);
		d[fr]++;
		d[to]++;
	}
}
int p[SIZEN][SIZEN]={0};
int dis[SIZEN][SIZEN];
void bfs(int x)
{
	deque<int> Q;
	dis[x][x]=0;
	Q.push_back(x);
	while(!Q.empty())
	{
		int v=Q.front();Q.pop_front();
		int tem=p[x][v];
		for(int i=0;i<s[v].size();i++)
		{
			int to=s[v][i];
			if(dis[x][to]==-1||(dis[x][v]+1==dis[x][to]&&tem<p[x][to]))
			{
				dis[x][to]=dis[x][v]+1;
				if(!tem) p[x][to]=to;
				else p[x][to]=tem;
				Q.push_back(to);
			}
		}
	}
}
double f[SIZEN][SIZEN]={0};
double DP(int x,int y)
{
	if(f[x][y]>zero) return f[x][y];
	if(x==y) return 0;
	if(p[x][y]==y||p[p[x][y]][y]==y) return f[x][y]=1;
	for(int i=0;i<s[y].size();i++)
	{
		int to=s[y][i];
		f[x][y]+=DP(p[p[x][y]][y],to);
	}
	f[x][y]+=DP(p[p[x][y]][y],y);
	f[x][y]/=(d[y]+1.0);
	f[x][y]+=1.0;
	return f[x][y];
}
int main()
{
	freopen("cchkk.in","r",stdin);
	freopen("cchkk.out","w",stdout);
	read();
	memset(dis,-1,sizeof(dis));
	for(int i=1;i<=N;i++) bfs(i);
	double ans=DP(C,M);
	printf("%.3lf\n",ans);
	return 0;
}