【BZOJ1415】[Noi2005]聪聪和可可
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
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
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。
题解：可以发现聪聪到可可的距离一定是越来越段的，这样就可以DP了。先预处理出tr[i][j]=k表示如果聪聪在i，可可在j，那么下一步聪聪会走到位置k。然后处理出所有二元组(i,j)代表聪聪和可可可能出现的位置，将二元组按照距离从小到大排序，然后DP即可。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1010;
int n,m,cnt,S,T,tot;
int to[maxn<<1],next[maxn<<1],head[maxn],pre[maxn],dis[maxn][maxn],tr[maxn][maxn],dim[maxn],d[maxn];
double f[maxn][maxn];
queue<int> q;
struct node
{
int a,b;
}p[maxn*maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmp(node a,node b)
{
return dis[a.a][a.b]<dis[b.a][b.b];
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void bfs(int tmp)
{
memset(d,-1,sizeof(d));
q.push(tmp),d[tmp]=0;
int u,i;
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i!=-1;i=next[i])
{
if(d[to[i]]==-1)
{
d[to[i]]=d[u]+1,pre[to[i]]=u;
q.push(to[i]);
}
else if(d[to[i]]==d[u]+1&&pre[to[i]]>u) pre[to[i]]=u;
}
}
for(i=1;i<=n;i++)
{
dis[i][tmp]=d[i];
if(d[i]>2) tr[i][tmp]=pre[pre[i]];
}
}
int main()
{
n=rd(),m=rd(),S=rd(),T=rd();
int i,j,a,b;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++) a=rd(),b=rd(),add(a,b),add(b,a),dim[a]++,dim[b]++;
for(i=1;i<=n;i++) bfs(i);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dis[i][j]!=-1) p[++tot].a=i,p[tot].b=j;
sort(p+1,p+tot+1,cmp);
for(i=1;i<=tot;i++)
{
a=p[i].a,b=p[i].b;
if(dis[a][b]<=2) f[a][b]=(dis[a][b]>0);
else
{
for(j=head[b];j!=-1;j=next[j]) f[a][b]+=(f[tr[a][b]][to[j]]+1)/(dim[b]+1);
f[a][b]+=(f[tr[a][b]][b]+1)/(dim[b]+1);
}
if(a==S&&b==T)
{
printf("%.3lf",f[S][T]);
return 0;
}
}
}