题解 | 绿豆蛙的归宿

message=[[0,0] for _ in range(n+1)]#值，概率

message[1][1]=1

先设最开始概率为1

message[v][1]+=curr_g*(1/n)

message[v][0]+=(curr_value/curr_g+w)*(1/n)*curr_g

print("{:.2f}".format(round(message[-1][0]/message[-1][1],2)))

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
in_size=[0]*(n+1)
out_point=[[] for _ in range(n+1)]
message=[[0,0] for _ in range(n+1)]#值，概率
message[1][1]=1
for _ in range(m):
    u,v,w=map(int,input().split())
    out_point[u].append((v,w))
    in_size[v]+=1
    
stack=[1]
while stack:
    u=stack.pop()
    if in_size[u]!=0:continue
    curr_value,curr_g=message[u]
    n=len(out_point[u])
    for v,w in out_point[u]:
        in_size[v]-=1
        stack.append(v)
        message[v][1]+=curr_g*(1/n)
        message[v][0]+=(curr_value/curr_g+w)*(1/n)*curr_g
print("{:.2f}".format(round(message[-1][0]/message[-1][1],2)))

#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> in_size(n + 1, 0);
    vector<vector<pair<int, int>>> out_point(n + 1);
    vector<pair<double, double>> message(n + 1, {0.0, 0.0}); // 值，概率
    
    message[1].second = 1.0; // 设置起始点的概率为1
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        out_point[u].push_back({v, w});
        in_size[v]++;
    }
    
    stack<int> stk;
    stk.push(1);
    
    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        
        if (in_size[u] != 0) continue;
        
        double curr_value = message[u].first;
        double curr_g = message[u].second;
        int out_size = out_point[u].size();
        
        for (auto& edge : out_point[u]) {
            int v = edge.first;
            int w = edge.second;
            
            in_size[v]--;
            stk.push(v);
            
            double prob = 1.0 / out_size;
            message[v].second += curr_g * prob;
            message[v].first += (curr_value / curr_g + w) * prob * curr_g;
        }
    }
    
    double result = message[n].first / message[n].second;
    cout << fixed << setprecision(2) << result << endl;
    
    return 0;
}