Tyvj1933绿豆蛙的归宿

给出一个有向无环图，起点为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 ;

 }