Description

给出一个有向无环的连通图，起点为1,终点为N，每条边都有一个长度。小A从起点出发，走向终点。

到达每一个顶点时，如果有K条离开该点的道路，小A可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。

现在小A想知道，从起点走到终点的所经过的路径总长度期望是多少？

Input

第一行: 两个整数 N M，代表图中有N个点、M条边

第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边

Output

从起点到终点路径总长度的期望值，四舍五入保留两位小数。

Sample Input

4 4

1 2 1

1 3 2

2 3 3

3 4 4

Sample Output

7.00

Hint

对于30%的数据  N<=50

对于70%的数据  N<=1000

对于100%的数据  N<=100000，M<=2*N，边权<=1000

 

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

测试数据：https://files.cnblogs.com/files/Syameimaru/tour.zip

-------------------------------------------------------------------------------------------------------

题解：

对于这道题，我们很容易想到，用动态规划的思想解决有关期望的问题。

可以观察到，每个店的期望值，都只与他的子节点有关，具体关系为：

f[i]=(f[j]+w)/d[i]

其中，f[i[表示从i节点，到达终点的路径的期望。

注意，这里我们不用f[i]表示到达i点概率的期望值，因为如果这样表示，会导致状态转移代价过大，使算法不够优秀，并且有更多的细节（只考虑能够到大的父节点计算入度），不够优秀，所以我们才用倒序来推。

时间复杂度 O(n),我们可以按照拓扑序倒序来转移。

当然，我们没必要真的进行拓扑排序，记忆化dp就好

下面是胡搞的代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define rep(i,a,b) for(register int i = (a);i<=(b);++i) 6 const int maxn = 120000 ; 7 struct Edge { 8     int v,dist; 9     Edge(int v,int dist):v(v),dist(dist){}10 };11 std::vector
          
            edges;12 std::vector
           
             G1[maxn],G2[maxn];13 std::queue
            
              Q,Q2;14 double f[maxn];15 int n,m,a,b,v,inq[maxn],tp[maxn];16 double dfs(int x) {17 if(f[x]) return f[x];18 if(x==n) return 0;19 for(register int i=0;i