\(N^2\)

DP[C][M]

废状态多

不好确定顺序

记忆化搜索

注意聪聪走编号小的点

#include 
    
     #include 
     
      using namespace std;const int MAXN=1011;const int MAXM=1011;const int INF=1034567890;int N, M;int S, T;int Dis[MAXN][MAXN];double F[MAXN][MAXN];bool Vis[MAXN][MAXN];struct Vert{    int FE;    int Dis;    int Bfn;    int Deg;} V[MAXN];struct Edge{    int x, y, next;} E[MAXM<<1];int Ecnt=0;void addE(int a, int b){    ++Ecnt;    E[Ecnt].x=a;E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;}int Q[MAXN], Head, Tail;int BFN=0;void BFS_init(){    Head=1;Tail=1;    ++BFN;}void BFS(int at){    BFS_init();    V[at].Dis=0;    Q[Tail++]=at;    V[at].Bfn=BFN;    while(Head
      
       0;k=E[k].next){            to=E[k].y;            if(V[to].Bfn==BFN)  continue;            V[to].Dis=V[at].Dis+1;            Q[Tail++]=to;            V[to].Bfn=BFN;        }    }}double DP(int s, int t){    if(s==t)    return 0.0;    if(Dis[s][t]<=2)    return 1.0;    if(Vis[s][t])   return F[s][t];    int s1=N+1, s1d=INF;    for(int k=V[s].FE, to;k>0;k=E[k].next){        to=E[k].y;        if(Dis[to][t]
       
        =INF)    return 1e9;    int s2=N+1, s2d=INF;    for(int k=V[s1].FE, to;k>0;k=E[k].next){        to=E[k].y;        if(Dis[to][t]
        
         =INF)    return 1e9;    double ret=1.0, p=1.0/(double)(V[t].Deg+1);    for(int k=V[t].FE, to;k>0;k=E[k].next){        to=E[k].y;        ret+=p*DP(s2, to);    }    ret+=p*DP(s2, t);    Vis[s][t]=true;F[s][t]=ret;    return ret;}int main(){    ios_base::sync_with_stdio(false);        cin >> N >> M;    cin >> S >> T;        for(int i=1, a, b;i<=M;++i){        cin >> a >> b;        addE(a, b);addE(b, a);        ++V[a].Deg;++V[b].Deg;    }        for(int i=1;i<=N;++i)        for(int j=1;j<=N;++j)            Dis[i][j]=INF;        for(int i=1;i<=N;++i){        BFS(i);        for(int j=1;j<=N;++j)            Dis[i][j]=V[j].Dis;    }        cout << fixed << setprecision(3) << DP(S, T) << endl;        return 0;}/*4 31 41 22 33 41.500*//*9 99 31 22 33 44 53 64 64 77 88 92.167*/