首页 > 试题广场 >

游游的旅行

[编程题]游游的旅行
  • 热度指数：953 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解


游游和小伙伴结伴而行，途径一处园林，游游与小伙伴决定进去游览。该园林可以看作一张个点（每个点代表一个景点）条边的无向图（无重边，无自环）。旅途中，两人的初始愉悦度皆为0 ，第 i个景点需要耗费分钟的时间，会让游游和小伙伴的愉悦度分别增加,  。每条边代表一条路径，第 i 条边连接编号为,  的两个景点，从走到或者从走到耗费的时间都是分钟。游游和小伙伴预计在该园林停留 分钟。检票进入园林后，游游和小伙伴会等概率的随机选择一个景点开始游览，每游览完一个景点后，游游和小伙伴会等概率的随机选择一个可以从当前景点直达的且来得及玩的景点作为下一个目的地。如果游览完一个景点后周围没有可以直达的且来得及游览的景点，游游和小伙伴就会提前结束游玩。 请分别计算出游游和小伙伴在游览结束后愉悦度的期望。  



输入描述:
第一行三个整数，分别表示, , ，以空格隔开；
接下来的行，每行三个整数，分别表示 ,, ，以空格隔开；
接下来的行，每行三个整数，分别表示, , ，以空格隔开。


输出描述:
输出一行实数，分别表示游游和小伙伴度的期望，精确到小数点后 5位，以空格隔开。
示例1

输入

5 4 60
25 12 83
30 38 90
16 13 70
22 15 63
50 72 18
2 1 7
3 1 7
4 3 1
5 3 10

输出

39.20000 114.40000

备注:
数据范围如下：
算法知识视频讲解
开通博客

暂无题解

问题信息

动态规划 算法工程师 图 携程 2019 大数据开发工程师
上传者：小小
难度：
5条回答 8612浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号