记录编号	425718	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]聪聪与可可	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2017-07-15 18:46:15	内存使用	15.61 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-8
int n,m,x,y,s,e;
vector<int>k[1001];
inline int read(){
	int sum=0;char ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum;
}
queue<int>q;
int f[1001][1001],to[1001][1001];bool t[1001];
void spfa(int x){
	memset(t,0,sizeof(t));
	q.push(x);t[x]=true;f[x][x]=0;
	while(!q.empty()){
		int o=q.front();q.pop();
		for(int i=0;i<k[o].size();++i){
			int oo=k[o][i];
			if(f[x][oo]>f[x][o]+1){
				f[x][oo]=f[x][o]+1;
				if(x==o)
					to[x][oo]=oo;
				else
				    to[x][oo]=to[x][o];
				if(!t[oo]){
					q.push(oo);
					t[oo]=true;
				}
			}
		}
		t[o]=false;	
	}
}
double jy[1001][1001];
double dfs(int s,int t){
	if(fabs(jy[s][t])>eps) return jy[s][t];
	if(s==t) return 0;
	if(f[s][t]<=2) return 1;
	int temp=s;
	s=to[s][t];	s=to[s][t];
	double num=0;
	for(int i=0;i<k[t].size();++i){
		int o=k[t][i];
		num+=dfs(s,o);
	}
	num+=dfs(s,t);
	num/=k[t].size()+1;num++;
	jy[temp][t]=num;
	return num;
}
int main(){
	freopen("cchkk.in","r",stdin);
	freopen("cchkk.out","w",stdout);
	memset(f,0x3f,sizeof(f));
	n=read();m=read();
	s=read();e=read();
	for(int i=1;i<=m;++i){
		x=read();y=read();
		k[x].push_back(y);
		k[y].push_back(x);
	}
	for(int i=1;i<=n;++i)
		sort(k[i].begin(),k[i].end());
	for(int i=1;i<=n;++i)
		spfa(i);
	printf("%.3lf\n",dfs(s,e));
	return 0;
}