| 题目名称 | 1065. [Nescafe19] 绿豆蛙的归宿 |
|---|---|
| 输入输出 | ldfrog.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-09-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：102， 提交：170， 通过率：60% | ||||
 HeHe |
100 | 0.075 s | 2.09 MiB | C++ |
 Hzoi_Mafia |
100 | 0.088 s | 2.26 MiB | C++ |
 Lethur |
100 | 0.088 s | 2.60 MiB | C++ |
 ~玖湫~ |
100 | 0.089 s | 1.96 MiB | C++ |
 BaDBoY |
100 | 0.094 s | 2.30 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.112 s | 5.27 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 0.113 s | 2.11 MiB | C++ |
|
BaDBoY |
100 | 0.138 s | 5.75 MiB | C++ |
 Lik |
100 | 0.141 s | 4.50 MiB | C++ |
 Furyton |
100 | 0.145 s | 4.51 MiB | C++ |
| 关于 绿豆蛙的归宿 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我觉得若是把有向边变为无向边……此题的难度便可加大。(同游走
 Shirry
2017-11-03 21:10
13楼
| ||||
|
题面修好了,迷之设定,只能改html才能改好...
还有...一直以为我不会犯那种边数达成点数的sb错误....  kZime
2017-08-15 20:45
12楼
| ||||
|
先求拓扑序再重新扫一遍的我感觉这做法有点傻w
我好菜啊QAQ | ||||
|
乱搜= =
| ||||
|
水dfs+概率
 | ||||
|
水题居然wa了3次。。。。
话说为什么加单向边邻接表开一倍还不行？？？ 数组小了居然会wa。。。 | ||||
|
纯暴力
| ||||
|
回复 @Hallmeow :
膜拜大佬。。。。→_→  Hzoi_QTY
2017-07-15 08:08
6楼
| ||||
|
倒着走还是好想……
HZOI_蒟蒻一只
2017-07-15 07:50
5楼
| ||||
|
好暴力啊……
HZOI_蒟蒻一只
2017-06-15 17:36
4楼
| ||||
rvalue
하루Kiev 【题目背景】
随着新版百度空间的下线，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
【数据范围】
对于20%的数据 N<=100
对于40%的数据 N<=1000
对于60%的数据 N<=10000
对于100%的数据 N<=100000，M<=2*N