本站独家赞助 青城博雅 IT校招就业考研-找青城博雅 特别优惠码 heaboy 

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

Memory Limit：256 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：Imported
Submit：0 Solved：0

Description

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

输入格式

第一行给出三个空格隔开的整数，分别表示 n,m,kn,m,kn,m,k
接下来的 nnn 行，每行三个空格隔开的整数，分别表示 ci,h1i,h2ic_i,h1_i,h2_ic​i​​,h1​i​​,h2​i​​
接下来的 mmm 行，每行三个空格隔开的整数，分别表示 xi,yi,tix_i,y_i,t_ix​i​​,y​i​​,t​i​​

输出格式

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

样例

样例输入

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≤100,1×60≤k≤8×600<n \leq 100, 1 \times 60 \leq k \leq 8 \times 600<n≤100,1×60≤k≤8×60
  • 10≤ci≤60,0<h1i,h2i≤10010 \leq c_i \leq 60, 0 < h1_i, h2_i \leq 10010≤c​i​​≤60,0<h1​i​​,h2​i​​≤100
  • 0<ti≤150 < t_i \leq150<t​i​​≤15
SubmitSubmit RecordStatisticsShowOff!