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