/ Vijos / 题库 /

夜夜的旅游计划

夜夜的旅游计划

背景

夜夜很贪玩。

描述

威尼斯是著名的水城。由n个岛和m座桥。岛从1到n编号。
夜夜是一名到威尼斯游玩的游客,她觉得每个岛都很有意思。因此她每次都会随机选择一个与当前岛相邻的岛去参观【同一座岛可以重复参观】。每座桥有一个权值At, 走过这座桥需要花费At个单位的时间, 桥可以双向通过。
夜夜初始在1号岛,她希望最终能到n号岛去。
那么夜夜到达n号岛的期望时间是多少呢?
答案保留一位小数。

格式

输入格式

第一行有两个整数n和m,表示岛屿个数与桥的个数。
之后m行,每行有三个整数u,v和At。其中1<=u,v<=n,表示有一座在岛u和岛v之间的桥,其权值为At。

输出格式

输出答案,答案四舍五入保留到一位小数。

样例1

样例输入1

3 3
1 2 1
2 3 1
3 1 1

样例输出1

2.0

样例2

样例输入2

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

样例输出2

16.0

限制

对于30%的数据
2<=n<=10
对于另外10%的数据
保证数据是一条链
对于另外10%的数据
保证数据是一个环,且1号岛与n号岛相连。
对于100%的数据
2<=n<=200
m<=n(n-1)/2
1<=At<=1000
数据保证每个岛和其余的都是联通的。且图中不存在重边。

每一个测试点时限1秒。

信息

ID
1966
难度
8
分类
d 点击显示
标签
(无)
递交数
496
已通过
42
通过率
8%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

夜夜的模拟赛之十三岁的梦想