记录编号	473990	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]聪聪与可可	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	0.212 s
提交时间	2017-11-09 15:27:51	内存使用	11.01 MiB

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1005
#define INF 1000000000
int dis[N][N],d[N],tar[N][N];
double f[N][N];bool vis[N];
int n,m,s,t,x,y;
queue<int> q;
vector<int> v[N];
inline void bfs(int s)
{
	q=queue<int>();
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[s]=0,q.push(s),vis[s]=1;
	tar[s][s]=s;
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		int top=v[tmp].size();
		for(int i=0,to;i<top;i++)
		  if(!vis[to=v[tmp][i]])
		  {
			if(tmp==s) tar[s][to]=to;
			else tar[s][to]=tar[s][tmp];
			vis[to]=1,d[to]=d[tmp]+1,q.push(to);
		  }
	}
	for(int i=1;i<=n;i++) dis[s][i]=d[i];
}
double dp(int s,int t)
{
	if(f[s][t]<INF) return f[s][t];
	if(s==t) return f[s][t]=0;
	if(dis[s][t]<3) return f[s][t]=1;
	int wh=tar[tar[s][t]][t];
	f[s][t]=dp(wh,t)+1;
	int top=v[t].size();
	for(int i=0;i<top;i++)
	  f[s][t]+=dp(wh,v[t][i])+1;
	f[s][t]/=v[t].size()+1.;
	return f[s][t];
}
int main()
{
	freopen("cchkk.in","r",stdin);
	freopen("cchkk.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	  scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
	for(int i=1;i<=n;i++) bfs(i);
	memset(f,70,sizeof(f));
	printf("%.3lf",dp(s,t));
	return 0;
}