[BZOJ] 1415: [Noi2005]聪聪和可可

先预处理出\(stp[x][y]\)表示聪聪在\(x\)，可可在\(y\)时，聪聪下一步走到哪里

设\(f[x][y]\)表示聪聪在\(x\)，可可在\(y\)时聪聪追到可可的期望步数，显然这是个倒推，由于边界较复杂，大力记搜就是最佳选择

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}
#define space putchar(' ')
#define nextline putchar('\n')
void _(int x){if(!x)return;_(x/10);putchar('0'+x%10);}
void out(int x){if(!x)return;else _(x);}

const int MAXN = 1005;

int n,m;
int nxt[MAXN<<1],to[MAXN<<1];
int ecnt,head[MAXN],deg[MAXN];
inline void add(int x,int y){
  nxt[++ecnt] = head[x];
  to[ecnt] = y;
  head[x] = ecnt;
  deg[x]++;
}
int cc,kk;

int dis[MAXN][MAXN];
queue<int> Q;
int inq[MAXN];
void bfs(int st){
  Q.push(st);dis[st][st]=0;
  while(!Q.empty()){
    int tp=Q.front();Q.pop();inq[tp]=0;
    for(int i=head[tp];i;i=nxt[i]){
      int v=to[i];
      if(dis[st][v]<=dis[st][tp]+1)continue;
      dis[st][v]=dis[st][tp]+1;
      Q.push(v);
    }
  }
}

int stp[MAXN][MAXN];
double f[MAXN][MAXN];
double dfs(int x,int y){
  if(f[x][y]>=0)return f[x][y];
  if(x==y) return f[x][y]=0.0;
  if(stp[x][y]==y) return f[x][y]=1.0;
  if(stp[stp[x][y]][y]==y) return f[x][y]=1.0;
  double &ret=f[x][y];
  ret=0.0;
  for(int i=head[y];i;i=nxt[i]){
    int v=to[i];
    ret+=dfs(stp[stp[x][y]][y],v);
  }
  ret+=dfs(stp[stp[x][y]][y],y);
  ret/=(deg[y]+1);ret++;
  return ret;
}

signed main(){
  memset(dis,0x3f,sizeof(dis));
  memset(stp,0x3f,sizeof(stp));
  memset(f,0xcf,sizeof(f));
  n=rd();m=rd();
  cc=rd();kk=rd();
  int x,y;
  for(int i=1;i<=m;i++){
    x=rd();y=rd();
    add(x,y);add(y,x);
  }
  for(int i=1;i<=n;i++)bfs(i);
  for(int i=1;i<=n;i++){
    for(int j=head[i];j;j=nxt[j]){
      int v=to[j];
      for(int k=1;k<=n;k++){
        if(dis[i][k]==dis[v][k]+1&&stp[i][k]>v){
          stp[i][k]=v;
        }
      }
    }
  }
  printf("%.3lf",dfs(cc,kk));
  return 0;
}