Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5467 --路径长度
5467: 路径长度
警告!
题目
状态
题解
题目描述
给出一张 $n$ 个点 $m$ 条边的有向无环图,起点为 $1$,终点为 $n$,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。 绿豆蛙从起点出发,走向终点。到达每一个顶点时,如果该节点有 $k$ 条出边,绿豆蛙可以选择任意一条边离开该点,并且走向每条边的概率为 $\frac{1}{k}$。现在绿豆蛙想知道,从起点走到终点所经过的路径总长度期望是多少?
输入
第一行有两个整数,分别代表图的点数 $n$ 和边数 $m$。 接下来 $m$ 行,每行有三个整数$u,v,w$ ,代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。
输出
输出一个实数,表示答案,保留两位小数。
样例输入输出
输入#1
复制
4 4 1 2 1 1 3 2 2 3 3 3 4 4
输出#1
复制
7.00
提示
对于 $20\%$ 的数据,保证 $n \leq 10^2$。 对于 $40\%$ 的数据,保证 $n \leq 10^3$。 对于 $60\%$ 的数据,保证 $n \leq 10^4$。 对于 $100\%$ 的数据,保证 $1\leq n \leq 10^5$,$1 \leq m \leq 2n$,$1 \leq u,v \leq n$,$1 \leq w \leq 10^9$,给出的图无重边和自环。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
数学期望
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和