记录编号	234931	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]聪聪与可可	最终得分	100
用户昵称	Fancy	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2016-03-09 20:10:16	内存使用	11.80 MiB

#include<cstring>
#include<cstdio>
#include<queue>
#define N 1001
using namespace std;
int n,m,S,T,ecnt=1,to[N*2],next[N*2],st[N],ds[N],du[N],g[N][N];
bool used[N];
double f[N][N];
queue<int> q;
void SPFA(int K)
{
	memset(ds,0x7f,sizeof(ds));
	memset(used,0,sizeof(used));
	q.push(K);ds[K]=0;used[K]=1;g[K][K]=K;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=st[x];i;i=next[i])
		{
			int y=to[i];
			if(!used[y]) used[y]=1,ds[y]=ds[x]+1,q.push(y);
			if(ds[y]<ds[g[x][K]]||(ds[y]==ds[g[x][K]]&&y<g[x][K])) g[x][K]=y;
		}
	}
}
double Search(int s,int t)
{
	if(s==t) return 0;
	if(g[s][t]==t||g[g[s][t]][t]==t) return 1;
	if(f[s][t]) return f[s][t];
	int C=g[g[s][t]][t];
	double ans=Search(C,t);
	for(int i=st[t];i;i=next[i]) ans+=Search(C,to[i]);
	return f[s][t]=ans/(du[t]+1)+1;
}
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,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		to[++ecnt]=y;next[ecnt]=st[x];st[x]=ecnt;du[x]++;
		to[++ecnt]=x;next[ecnt]=st[y];st[y]=ecnt;du[y]++;
	}  
	for(int i=1;i<=n;i++) SPFA(i);
	printf("%.3lf",Search(S,T));
	return 0;
}