題目大意：給定 $DAG$ 帶邊權連通圖，保證所有點都能到達終點 $n$，每個點等概率沿邊走，求起點 $1$ 到終點?$n$ 的期望長度。
題解：拓撲，然后倒著$DP$就可以了
卡點：無
?
C++ Code：
#include <cstdio>
#define maxn 100010
using namespace std;
int n, m, oud[maxn], vis[maxn];
int q[maxn], h, t;
double f[maxn];
int head[maxn], cnt;
struct Edge {int to, nxt, w;
} e[maxn << 1];
void add(int a, int b, int c) {e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
}
int main() {scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(b, a, c);oud[a]++;vis[a]++;}f[q[h = t = 0] = n] = 0;while (h <= t) {int u = q[h++];for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;f[v] += (f[u] + e[i].w) / oud[v];--vis[v];if (!vis[v]) q[++t] = v;}}printf("%.2lf\n", f[1]);return 0;
}
