记录编号 |
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;
}