P4316 绿豆蛙的归宿

    • 958通过
    • 1.6K提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 拓扑排序 期望 递归
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    「Poetize3」

    题目背景

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

    题目描述

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4 4 
    1 2 1 
    1 3 2 
    2 3 3 
    3 4 4
    输出样例#1: 复制
    7.00

    说明

    对于20%的数据 N<=100

    对于40%的数据 N<=1000

    对于60%的数据 N<=10000

    对于100%的数据 N<=100000,M<=2*N

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。