问题 23817 --sightsee

23817: sightsee

时间限制: 1 Sec  内存限制: 128 MB
提交: 66  解决: 26
[提交][状态][讨论版][命题人:]

题目描述

作为对奶牛们辛勤工作的回报,Farmer John 决定带她们去附近的大城市玩 一天。旅行的前
夜,奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。 很幸运地,奶牛们找到了一张详
细的城市地图,上面标注了城市中所有 L(2 <= L <= 1000)座标志性建筑物(建筑物按 1..L 顺
次编号),以及连接这些建筑 物的 P(2 <= P <= 5000)条道路。按照计划,那天早上 Farmer John
会开车将奶牛们送到某个她们指定的建筑物旁边,等奶牛们完成她们的整个旅行并回到出发
点后,将她们接回农场。由于大城市中总是寸土寸金,所有的道路都很窄,政府不 得不把
它们都设定为通行方向固定的单行道。 尽管参观那些标志性建筑物的确很有意思,但如果
你认为奶牛们同样享受穿 行于大城市的车流中的话,你就大错特错了。与参观景点相反,
奶牛们把走路定 义为无趣且令她们厌烦的活动。对于编号为 i 的标志性建筑物,奶牛们清
楚地知道参观它能给自己带来的乐趣值 F_i (1 <= F_i <= 1000)。相对于奶牛们在走路上花的
时间,她们参观建筑物的耗时可以忽略不计。 奶牛们同样仔细地研究过城市中的道路。她
们知道第 i 条道路两端的建筑物 L1_i 和 L2_i(道路方向为 L1_i -> L2_i),以及她们从道路
的一头走到另一头所 需要的时间 T_i(1 <= T_i <= 1000)。 为了最好地享受她们的休息日,
奶牛们希望她们在一整天中平均每单位时间 内获得的乐趣值最大。当然咯,奶牛们不会愿
意把同一个建筑物参观两遍,也就 是说,虽然她们可以两次经过同一个建筑物,但她们的
乐趣值只会增加一次。顺 便说一句,为了让奶牛们得到一些锻炼,Farmer John 要求奶牛们
参观至少 2 个建筑物。 请你写个程序,帮奶牛们计算一下她们能得到的最大平均乐趣值。

输入

* 第 1 行: 2 个用空格隔开的整数:L 和 P
* 第 2..L+1 行: 第 i+1 行仅有 1 个整数:F_i
* 第 L+2..L+P+1 行: 第 L+i+1 行用 3 个用空格隔开的整数:L1_i,L2_i 以及 T_i, 描述了
第 i 条道路。

输出

* 第 1 行: 输出 1 个实数,保留到小数点后 2 位(直接输出,不要做任何特殊的取整操作),
表示如果奶牛按题目中描述的一系列规则来安排她们的旅行的话,她们能获得的最大平均乐
趣值

样例输入

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

样例输出

6.00

来源

 

[提交][状态]