1065. [Nescafe19] 绿豆蛙的归宿

★ 输入文件：ldfrog.in 输出文件：ldfrog.out 简单对比
时间限制：1 s 内存限制：128 MB

【背景】

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

【题目描述】

给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

【输入格式】

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

【输出格式】

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

【输入样例】

4 4
1 2 1
1 3 2
2 3 3
3 4 4

【输出样例】

7.00

【时限】

各个测试点1s

【数据范围】

对于20%的数据 N<=100
对于40%的数据 N<=1000
对于60%的数据 N<=10000
对于100%的数据 N<=100000，M<=2*N

/*

期望=概率*贡献.

然后把贡献停留在点上最后累加.

*/

#include<cstdio>

using namespace std;

const int N=1e5+;

struct edge{int v,w,next;}e[N<<];int tot,head[N];

int m,n,out[N];

double s[N],ans[N],res;

void add(int x,int y,int z){

    e[++tot].v=y;

    e[tot].w=z;

    e[tot].next=head[x];

    head[x]=tot;

}

void dp(int x){

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].v;

        s[v]=s[x]/out[x];

        dp(v);

        ans[x]+=s[v]*e[i].w;

    }

}

int main(){

    freopen("ldfrog.in","r",stdin);

    freopen("ldfrog.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=,x,y,z;i<=m;i++){

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);out[x]++;

    }

    s[]=;

    dp();

    for(int i=;i<=n;i++) res+=ans[i];

    printf("%.2lf",res);

    return ;

}

巴特西

1065. [Nescafe19] 绿豆蛙的归宿（概率）