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就好
下面是胡搞的代码：
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define rep(i,a,b) for(register int i = (a);i<=(b);++i)
const int maxn = ;
struct Edge {
int v,dist;
Edge(int v,int dist):v(v),dist(dist){}
};
std::vector<Edge> edges;
std::vector<int> G1[maxn],G2[maxn];
std::queue<int> Q,Q2;
double f[maxn];
int n,m,a,b,v,inq[maxn],tp[maxn];
double dfs(int x) {
if(f[x]) return f[x];
if(x==n) return ;
for(register int i=;i<G1[x].size();i++) {
Edge e = edges[G1[x][i]];
f[x]+=dfs(e.v)+e.dist;
}
f[x]/=G1[x].size();
return f[x];
}
int main() {
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,m){
scanf("%d%d%d",&a,&b,&v);
inq[b]++;edges.push_back(Edge(b,v));
edges.push_back(Edge(a,v));
int num = edges.size();
G1[a].push_back(num-);
G2[b].push_back(num-);
}
dfs();
printf("%.2lf",f[]);
return ;
}