求期望一般倒推

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>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));}