bzoj 1415 [Noi2005]聪聪和可可

1415: [Noi2005]聪聪和可可

Time Limit: 10 Sec  Memory Limit: 162 MB
[Submit][Status][Discuss]

Description

Input

数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。 接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output

输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Sample Input

【输入样例1】
4 3
1 4
1 2
2 3
3 4
【输入样例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output

【输出样例1】
1.500
【输出样例2】
2.167

HINT

【样例说明1】
开始时，聪聪和可可分别在景点1和景点4。
第一个时刻，聪聪先走，她向更靠近可可(景点4)的景点走动，走到景点2，然后走到景点3；假定忽略走路所花时间。
可可后走，有两种可能：
第一种是走到景点3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为1，概率为 。
第二种是停在景点4，不被吃掉。概率为 。
到第二个时刻，聪聪向更靠近可可(景点4)的景点走动，只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1* +2* =1.5步。


对于所有的数据，1≤N,E≤1000。
对于50%的数据，1≤N≤50。

Solution

f[i][j]表示聪聪在i点，可可在j点，聪聪吃掉可可的期望时间

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#define nn 1011
#define mm 2011
#define inf 100000000
using namespace std;
double f[nn][nn];
int fir[nn],nxt[mm],to[mm],du[nn],dis[nn][nn],e=0;
struct node{
	int wo,di;
	node(int wo=0,int di=0){
		this->wo=wo;this->di=di;
	}
	bool operator<(const node&x)const{
		return di>x.di;
	} 
}zc,ne;
priority_queue<node> q;
int read()
{
	int ans=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}
	return ans*f;
}
void add(int u,int v)
{
	nxt[++e]=fir[u];fir[u]=e;to[e]=v;du[u]++;
	nxt[++e]=fir[v];fir[v]=e;to[e]=u;du[v]++;
}
void dijstra(int x)
{
	memset(dis[x],127,sizeof(dis[x]));
	dis[x][x]=0;
	zc.wo=x;zc.di=0;
	q.push(zc);
	while(!q.empty())
	{
		zc=q.top();q.pop();
		for(int i=fir[zc.wo];i;i=nxt[i])
		  if(dis[x][to[i]]>zc.di+1)
		  {
		  	dis[x][to[i]]=zc.di+1;
		  	ne.wo=to[i];ne.di=dis[x][to[i]];
		  	q.push(ne);
		  }
	}
}
double dp(int c,int k)
{
	int cc=c;
	if(f[c][k]) return f[c][k];
	if(c==k) return 0;
	int mi=inf,nod;
	for(int i=fir[c];i;i=nxt[i])
	  if(dis[to[i]][k]<mi||(dis[to[i]][k]==mi&&to[i]<nod))
	  {
	  	mi=dis[to[i]][k];
	  	nod=to[i];
	  }
	c=nod;
	if(c==k) return f[cc][k]=1.0;
	mi=inf,nod;
	for(int i=fir[c];i;i=nxt[i])
	  if(dis[to[i]][k]<mi||(dis[to[i]][k]==mi&&to[i]<nod))
	  {
	  	mi=dis[to[i]][k];
	  	nod=to[i];
	  }
	c=nod;
	if(c==k) return f[cc][k]=1.0;
	double ans=0;
	for(int i=fir[k];i;i=nxt[i])
	  ans+=(dp(c,to[i])+1)*1.0/(double)(du[k]+1);
	ans+=(dp(c,k)+1)*1.0/(double)(du[k]+1);
	return f[cc][k]=ans;
}
int main()
{
	double res;
	int n,m,c,k,u,v;
	n=read();m=read();
	c=read();k=read();
	for(int i=1;i<=m;i++)
	{
		u=read();v=read();add(u,v);
	}
	for(int i=1;i<=n;i++)
	  dijstra(i);
	res=dp(c,k);
	printf("%.3lf",res);
	return 0;
}