给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
咕咕咕了大量知识点的总结后，写一篇题的解题报告
在被lyd的大量BT例题虐杀后，看到这么一道题，那是激动，直接秒了（假假
题解：
f[x]表示以x为起点走到终点的路径总长度期望
设从x连出去的边y1, y2, y3, ..., yk, 路径长度为z1, z2, z3, ..., zk
很容易想到式子为:
f[x] = 1/k * Σ(f[yi]+zi)(1<=i<=k)
意会一下觉得需要建一个反图
然后在反图上执行拓扑排序，在拓扑排序的同时计算期望
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define uint unsigned int
using namespace std;
const int maxn = , maxm = ;
struct shiki {
int y, net, val;
}e[maxm << ];
int lin[maxn], len = ;
int n, m;
int K[maxn], in[maxn];
double f[maxn];
queue<int> q; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline void insert(int xx, int yy, int v) {
e[++len].y = yy;
e[len].net = lin[xx];
e[len].val = v;
lin[xx] = len;
} int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
n = read(), m = read();
for(register uint i = ; i <= m; ++i) {
int x = read(), y = read(), z = read();
insert(y, x, z);
K[x]++, in[x]++;//反图上连向x的边数和反图上x的入度，也就是原图x连出的边数和x的出度
}
q.push(n);
while(!q.empty()) {
int k = q.front(); q.pop();
for(int i = lin[k]; i; i = e[i].net) {
int to = e[i].y;
f[to] += (f[k] + e[i].val) / K[to];
in[to]--;
if(!in[to]) q.push(to);
}
}
printf("%0.2f", f[]);
return ;
}