洛谷P4316 绿豆蛙的归宿

题目背景
随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述
给出张 nn 个点 mm 条边的有向无环图，起点为 11，终点为 nn，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 kk 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \frac{1}{k}
k
1
​
。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式
输入的第一行是两个整数，分别代表图的点数 nn 和边数 mm。

第 22 到第 (m + 1)(m+1) 行，每行有三个整数 u, v, wu,v,w，代表存在一条从 uu 指向 vv 长度为 ww 的有向边。

输出格式
输出一行一个实数代表答案，四舍五入保留两位小数。

输入输出样例
输入 #1复制
4 4
1 2 1
1 3 2
2 3 3
3 4 4
输出 #1复制
7.00
说明/提示
数据规模与约定
对于 20%20% 的数据，保证 n \leq 10^2n≤10
2
。
对于 40%40% 的数据，保证 n \leq 10^3n≤10
3
。
对于 60%60% 的数据，保证 n \leq 10^4n≤10
4
。
对于 100%100% 的数据，保证 1 \leq n \leq 10^51≤n≤10
5
，1 \leq m \leq 2 \times n1≤m≤2×n，1 \leq u, v \leq n1≤u,v≤n，1 \leq w \leq 10^91≤w≤10
9
，给出的图无重边和自环。
上代码：

#include
#include
#include
#define MAXN 200000
#define res register
using namespace std;
struct node{
	int next,to,val;
}e[MAXN<<1];
int n,m,tot,vis[MAXN],head[MAXN],r[MAXN];
double dp[MAXN];
inline void add(int x,int y,int c){
	e[++tot].next=head[x];
	e[tot].to=y;
	e[tot].val=c;
	head[x]=tot;
}
void dfs(int x){
	if(x==n){
		dp[x]=0;
		return;
	}
	if(vis[x])return;
	vis[x]=1;
	for(res int i=head[x];i;i=e[i].next){
		int v=e[i].to;
		dfs(v);
		dp[x]+=(dp[v]+e[i].val)/r[x]*1.0;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++){
		res int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		r[a]++;
	}dfs(1);
	printf("%.2lf\n",dp[1]);
	return 0;
}```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42