题解 | 绿豆蛙的归宿

有向无环图是个很好的性质。因为期望dp都是逆推，所以可以建反图，然后在反图上拓扑排序来递推。设表示点到终点的期望路径长度，有,为点的度数。答案为

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

double f[N];
int n, m, du[N], in[N];
int cnt, head[N], q[N];
struct edge {int to, nxt, v;} e[N];

void ins(int u, int v, int w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int u, v, w, i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w); 
        in[u]++; du[u]++; ins(v, u, w);
    }
    int l = 1, r = 1;
    q[r++] = n;
    while(l < r) {
        int u = q[l++];
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            f[v] += (double) (f[u] + e[i].v) / du[v];
            in[v]--;
            if(!in[v]) q[r++] = v;
        }
    }
    printf("%.2lf\n", f[1]);
}