题意：小兔子乖乖~~~

题意·真：无向图吗，聪抓可，每个时间聪先走可后走，聪一次可以走两步，朝着里可最近且点编号最小的方向；可一次只一步，等概率走向相邻的点或不走

求聪抓住可的期望时间

---

 

和游走很像，只不过这道题限制了一个人走的方向，两人间的距离具有了阶段性!可以直接$DP$

求期望一般倒推

$f[i][j]$表示聪在$i$可在$j$抓住的期望时间

$bfs$预处理$g[i][j]$表示聪在$i$可在$j$下一步聪走到哪里

这样聪的行动就知道了，转移枚举可的行动就行啦

边界：$f[i][i]=0,\ f[i][j]=1:g[i][j]=j or g[g[i][j]][j]=j$

 

另一种做法：相信世界是善良的，永远输出正无穷

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=1005;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,m,a,b,de[N],u,v;struct edge{    int v,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}int g[N][N];int q[N],head,tail,d[N][N];bool inq[N];inline void lop(int &x){
   if(x==N) x=1;}void bfs(int s,int *g,int *d){    head=tail=1;    memset(inq,0,sizeof(inq));    q[tail++]=s; d[s]=0; inq[s]=1;    while(head!=tail){        int u=q[head++];inq[u]=0;lop(head);        for(int i=h[u];i;i=e[i].ne){            int v=e[i].v;            if(d[v]>d[u]+1 || (d[v]==d[u]+1&&g[v]>g[u])){                d[v]=d[u]+1;                g[v]= g[u]==0 ? v : g[u];                if(!inq[v]) q[tail++]=v,inq[v]=1,lop(tail);            }        }    }}double f[N][N];double dfs(int a,int b){
   //printf("dfs %d %d\n",a,b);    if(a==b) return 0;    if(g[a][b]==b || g[ g[a][b] ][b]==b) return 1;    if(f[a][b]) return f[a][b];    double &re=f[a][b];    int t=g[ g[a][b] ][b];    re=dfs(t,b);    for(int i=h[b];i;i=e[i].ne)    re+=dfs(t,e[i].v);    re=re/(de[b]+1)+1;    return re;}int main(){    freopen("in","r",stdin);    n=read();m=read();a=read();b=read();    for(int i=1;i<=m;i++) u=read(),v=read(),de[u]++,de[v]++,ins(u,v);    memset(d,127,sizeof(d));    for(int i=1;i<=n;i++) bfs(i,g[i],d[i]);    //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("g %d %d  %d\n",i,j,g[i][j]);    printf("%.3lf",dfs(a,b));}