TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4257
  • 题目
  • P4257死宅与陷阱
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    starkmal是个死宅。

    由于starkmal经常在竞赛课上把自己和别人的桌面换成奇奇怪怪的动图,对你的身体健康造成了不良影响,你和其他同学决定在他回家的路上修理他。

    通过长期的观察,你发现了starkmal回家路线的一些规律,并绘制了一张地图。在地图上,有他回家可能会经过的N个点,编号为1~N。这些点之间连有M条边,表示两点间有一条道路。两点之间至多存在一条边。由于特殊的原因,这些边是有向的。由于starkmal并不喜欢兜圈子,所以这幅地图上不存在从某点出发能回到该点的路径。

    这一天,starkmal上完竞赛课从科学馆(编号为S)出发回家,由于比较疲惫,他今天想要先随便走走。你在长期的观察中已经掌握了starkmal的习性,知道了他选择每条道路的概率。你的同伙已经在地图上的每个点上安放了陷阱,第i号节点的陷阱能对starkmal造成Vi的伤害。现在你手上有T个陷阱,每个陷阱可以追加P的伤害。由于大小关系,每个节点只能至多再放一个陷阱。由于科学馆的安保工作非常到位,你不能在科学馆处放陷阱,但是同伙的陷阱仍然可以对starkmal造成伤害。

    starkmal已经非常疲惫,他遇到陷阱一定会中招。你想知道把手中的陷阱经过合适的安放后能对他造成伤害的最大期望值。你并不需要考虑他从哪里回家、怎样回家。

    输入格式

    第一行包含五个非负整数N,M,P,S,T。分别代表点的个数、边的条数、你手中的每个陷阱可以增加的伤害、科学馆编号、你拥有的陷阱个数。

    第二行包含N个整数,分别代表1~N号节点的上陷阱能造成的伤害Vi。

    接下来M行,每行包含两个整数ai,bi和一个实数ci,分别表示边的起点、终点、在起点处选择走该边的概率。Ci为一个两位小数。

    输出格式

    仅一行,包含一个实数,表示操作之后能得到的最大期望伤害。输出时保留三位小数。

    样例输入

    4 3 30 1 1
    10 50 20 10
    1 2 0.80
    1 3 0.10
    2 4 0.60

    样例输出

    80.800

    提示

    【数据范围】

     

    对于30%的数据,1≤N≤1000,1≤M≤1000,T=1。

    存在10%的数据,P=0。

    对于100%的数据,1≤N≤100000,1≤M≤100000,0≤P≤2000,1≤T<N,0.00≤ci≤1.00,

    1≤S,ai,bi≤N,1≤Vi≤1000。输入数据保证以某个节点为起点的所有边的概率总和不大于1,也就是说,他可能一条边也不走,到了这个节点就停止。

     


    来源  OBlack rgnoH