#6178. 「美团 CodeM 初赛 Round B」景区路线规划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: gzgywh

题目描述

游乐园被描述成一张 n 个点, m 条边的无向图(无重边,无自环)。每个点代表一个娱乐项目,第 i 个娱乐项目需要耗费 c_i 分钟的时间,会让小 y 和妹子的开心度分别增加 h1_i , h2_i ,他们俩初始的开心度都是 0 。每条边代表一条路,第 i 条边连接编号为 x_i , y_i 的两个娱乐项目,从 x_i 走到 y_i 或者从 y_i 走到 x_i 耗费的时间都是 t_i 分钟。小 y 和妹子预计在游乐园里玩 k 分钟。最开始的时候,小 y 和妹子会等概率的随机选择一个娱乐项目开始玩,每玩完一个项目后,小 y 和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目,小 y 和妹子就会提前结束游玩。 请你分别计算小 y 和妹子在游玩结束后开心度的期望。

输入格式

第一行给出三个空格隔开的整数,分别表示 n,m,k
接下来的 n 行,每行三个空格隔开的整数,分别表示 c_i,h1_i,h2_i
接下来的 m 行,每行三个空格隔开的整数,分别表示 x_i,y_i,t_i

输出格式

两个用空格隔开的实数,分表表示小 y 和妹子开心度的期望,精确到小数点后 5 位。

样例

样例输入

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

数据范围与提示

  • 0<n \leq 100, 1 \times 60 \leq k \leq 8 \times 60
  • 10 \leq c_i \leq 60, 0 < h1_i, h2_i \leq 100
  • 0 < t_i \leq15