记录编号 |
59487 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOI 2005]聪聪与可可 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.180 s |
提交时间 |
2013-05-07 21:20:46 |
内存使用 |
12.34 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include<algorithm>
using namespace std;
const int SIZEN=1001,INF=0x7fffffff;
int N,M;//节点数,道路数,也就是题中的N,E
int CC,KK;//猫和老鼠的初始位置
deque<int> c[SIZEN];//邻接表(终于写了个这么痛快的邻!接!表!)
//下标从1开始
int near[SIZEN][SIZEN]={0};//near[i][j]表示从j尽量接近i的走两步走到的位置
bool worked[SIZEN]={0};//是否对i求过最短路
double f[SIZEN][SIZEN]={0};
void BFS(int s){
if(worked[s]) return;
worked[s]=true;
bool visit[SIZEN]={0};
int father[SIZEN]={0};
int best[SIZEN]={0};
int x,y,i;
for(i=1;i<=N;i++){
if(i!=s) best[i]=INF;
}
deque<int> Q;
Q.push_back(s),visit[s]=true;
near[s][s]=s;
while(Q.size()){
x=Q.front(),Q.pop_front();
for(i=0;i<c[x].size();i++){
y=c[x][i];
if(visit[y]) continue;
if(x==s) near[s][y]=y;
else near[s][y]=near[s][x];
visit[y]=true;
Q.push_back(y);
}
}
}
void read(void){
scanf("%d%d",&N,&M);
scanf("%d%d",&CC,&KK);
int i,j,a,b;
for(i=1;i<=N;i++) c[i].push_back(i);
for(i=1;i<=M;i++){
scanf("%d%d",&a,&b);
c[a].push_back(b),c[b].push_back(a);
}
for(i=1;i<=N;i++){
for(j=1;j<i;j++){
f[i][j]=f[j][i]=-1;
}
}
for(i=1;i<=N;i++) sort(c[i].begin(),c[i].end());
for(i=1;i<=N;i++) BFS(i);
}
double DP(int s,int t){
if(f[s][t]!=-1) return f[s][t];
int i;
double sum=0;
int next=near[near[s][t]][t];
if(next==t){
f[s][t]=1;
return 1;
}
for(i=0;i<c[t].size();i++){
sum+=DP(next,c[t][i]);
}
sum/=(double)c[t].size();
sum++;
f[s][t]=sum;
return sum;
}
int main(){
freopen("cchkk.in","r",stdin);
freopen("cchkk.out","w",stdout);
read();
double ans=DP(CC,KK);
cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
return 0;
}