题解 | 绿豆蛙的归宿

想好路径期望怎么计算之后，使用 DFS 记忆化搜索就好

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;
struct E{
    ll id;
    double w;
};
vector<vector<E>>adj(N);
vector<double>vis(N,-1);
ll n,m;

void dfs(ll x){
    if(adj[x].size()==0||x==n){
        vis[x]=0;
        return;
    }
    double t=1/(double)adj[x].size();
    double sum=0;
    for(auto it:adj[x]){
        if(vis[it.id]==-1){
            dfs(it.id);
        }
        sum+=vis[it.id]+it.w;
    }
    vis[x]=sum*t;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll u,v;
        double w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
    }
    dfs(1);
    printf("%.2lf",vis[1]);

    return 0;
}