Description
随着新版百度空間的下線，Blog寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。
給出一個有向無環的連通圖，起點為1終點為N，每條邊都有一個長度。綠豆蛙從起點出發，走向終點。
到達每一個頂點時，如果有K條離開該點的道路，綠豆蛙可以選擇任意一條道路離開該點，并且走向每條路的機率為 1/K 。
現在綠豆蛙想知道，從起點走到終點的所經過的路徑總長度期望是多少？
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
對于100%的資料 N<=100000，M<=2*N
傳送門
第一道期望題……
感覺對于“期望”這個概念的了解還有待提升。
#include<bits/stdc++.h>
using namespace std;
const int
N=100005;
int n,m,Ecnt,son[N];
bool vis[N];
double dp[N];
struct Edge{
int next,to,val;
}E[N<<1];int head[N];
void add(int u,int v,int w){
E[++Ecnt].next=head[u];
E[Ecnt].to=v;
E[Ecnt].val=w;
head[u]=Ecnt;
son[u]++;
}
void dfs(int u){
vis[u]=1,dp[u]=0.0;
for (int i=head[u];i;i=E[i].next){
int v=E[i].to;
if (!vis[v]) dfs(v);
dp[u]+=dp[v]+E[i].val;
}
if (son[u]) dp[u]/=(double)son[u];
}
int main(){
scanf("%d%d",&n,&m);
int x,y,z;
for (int i=1;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),add(x,y,z);
dfs(1);
printf("%.2lf\n",dp[1]);
return 0;
}