记录编号 59487 评测结果 AAAAAAAAAA
题目名称 [NOI 2005]聪聪与可可 最终得分 100
用户昵称 Gravatarcstdio 是否通过 通过
代码语言 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;
}