P7874钱借kzsn | ||
|
问题描述
kzsn最近在玩一款叫“大富翁”的小游戏,游戏虽然困难,但kzsn仍旧乐此不疲。
这天,kzsn在玩大富翁时天降横祸,股票支支高台跳水,股价狂跌,kzsn想凭借自己作为股神的高超技术进行操作,但是钱全部被套牢了,如果再这样下去,kzsn马上就要破产了。他只能赶紧去银行贷款。
银行贷款需要kzsn有一定的资质或者抵押。kzsn全部家当都在股市里了,没有东西抵押。
银行处于1号位置,kzsn每天行进的速度为v。这些位置之间有m条双行道连接。如果kzsn要贷款,就必须完成行长的任务——从银行出发,走过全地图的每一个位置。
这样来回跑会花费很多时间,好在kzsn还有很多的道具卡,可以瞬间回到上一个路口,这个道具卡可以无限使用。
Ambition眼看kzsn要破产了,自然要落井下石,乘人之危,乘虚而入,所以他在一些地方放置了路障、炸弹等障碍。
如果kzsn从这些道路上走过,他有两种选择:
1、横冲直撞,这样速度不会变,但是有s%的几率会受伤并原地休息d天(休息完后他仍然需要以原速度走完这条路);
2、小心绕过,这样速度将会减慢u[i],但是不会受伤。
不过不是人人都如Ambition一样作恶多端——“奶茶向”Aurora是“加油企业”的董事长,她在游戏中开了t家奶茶店,分别处于p[1]、p[2]……p[t]处,她听闻kzsn正面临破产的危机,决定施以援手。
Aurora会在奶茶店两旁的道路都为kzsn准备“加油奶茶”,可以让她分别在这两条路上行进速度增加w[i](虽然都是Aurora旗下的店铺,但是不同店铺奶茶份量不同,所以增幅效果也不同)。
kzsn想知道,以自己的速度最快完成行长任务的期望值是多少天?
输入格式
第1行输入n,m,t,v。
第2行t个数,依次输入p[i]。
第3行t个数,依次输入w[i]。
第4行到第m+3行,先输入x。如果x为1代表是正常道路,x为2代表是被Ambition阻拦的路。输入a,b,c分别代表道路两端、长度。如果x为2,再输入u,s和d。
输出格式
1行,期望值,保留9位小数。数据保证kzsn一定能完成任务,无自环。
样例输入 1
4 4 2 2
1 4
2 10
1 1 2 5
2 2 4 7 1 80 5
1 2 3 4
1 3 4 2
样例输出 1
2.053030303
样例输入 2
3 2 0 1
1 1 2 3
2 1 3 1 2 100 1
样例输出 2
5.000000000
提示
1<=a,b,p[i],n<=10000 0<=m<=300000 0<=w[i],u[i],t<=100 0<v<=100 1<=c<=1000
0<=s<=100 0<=d<=10
10%的数据满足m=n-1
另外20%的数据满足x恒为1
另外20%的数据满足t=0
同时以上50%的数据都满足n<=1000,m<=10000
前60%的数据时限1s
后40%的数据时限1.5s