#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>d[105];
long long dis[105],vis[105],cnt[105],ans;
long long cts[105];
long long dfs(int p){
    if(cnt[p])
        return cnt[p];
    int res=0;
    for(int i=0;i<d[p].size();i++)
        if(dis[d[p][i]]+1==dis[p]){
            res+=dfs(d[p][i])*cts[p]/cts[d[p][i]];
        }
    return cnt[p]=res;
}
int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        d[x].push_back(y);
        d[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        dis[i]=2147483647;
    dis[1]=0;
    queue<int>que;
    que.push(1);
    while(!que.empty()){
        int cur=que.front();
        que.pop();
        for(int i=0;i<d[cur].size();i++)
            if(dis[d[cur][i]]>dis[cur]+1){
                dis[d[cur][i]]=dis[cur]+1;
                que.push(d[cur][i]);
            }
    }
    while(!que.empty())
        que.pop();
    que.push(n);
    cts[n]=1;
    while(!que.empty()){
        int cur=que.front();
        que.pop();
        for(int i=0;i<d[cur].size();i++)
            if(dis[d[cur][i]]+1==dis[cur]){
                if(cts[d[cur][i]]==0)
                    que.push(d[cur][i]);
                cts[d[cur][i]]+=cts[cur];
            }
    }
    cnt[1]=cts[1];
    dfs(n);
    for(int i=2;i<n;i++)
        cnt[i]*=2;
    for(int i=1;i<=n;i++)
        ans=max(ans,cnt[i]);
    cout<<fixed<<setprecision(12)<<1.0*ans/cts[1];
}

CF上Test22TLE了,但是不清楚原因，detail里面只显示TLE2000ms，内存竟然是0kb。

理论上，这个代码的复杂度是O(n)，但是我又找不到哪里有死循环。