题解 | 绿豆蛙的归宿

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i < m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].push_back({b, c});
    }
    ld ans = 0;
    auto dfs = [&](auto&& self, int x, int fa, int path, ll p) -> void{
        if (x == n - 1){
            ans += 1.0 * path / p;
            return ;
        }
        for (auto& [y, w]: g[x]){
            int k = g[x].size();
            self(self, y, x, path + w, p * k);
        }
    };
    dfs(dfs, 0, -1, 0, 1);
    cout << fixed << setprecision(2) << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}