Comet OJ

C0909 [JLOI2014]路径规划

内存限制：256 MB 时间限制：1000 ms

题目描述

相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。

考虑到实际情况，一辆车加满油能开的时间有限，所以在地图上增加了几个加油站。

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过 $k$ 个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。

注意：题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油。

相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。

考虑到实际情况，一辆车加满油能开的时间有限，所以在地图上增加了几个加油站。

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过$k$个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。

注意：题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油。

输入格式

第一行输入五个整数 $n$，$m$，$k$，$\mathrm{limit}$，$\mathrm{cost}$，表示有 $n$ 个点 $m$ 条边，车能开 $\mathrm{limit}$ 长的时间，及加油所花时间 $\mathrm{cost}$。

接下来 $n$ 行输入每个点信息，包括点的名称（名字中含有 “gas” 的为加油站。“start” 为起点，“end” 为终点），及以 $a$，$b$ 两个正整数表示红绿灯信息，若 $a$ 为 0 则表示没有红绿灯，$a$ 表示红灯时长，$b$ 表示绿灯时长。

接下来 $m$ 行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。

输出

一行输出最少平均花费时长。答案请保留三位小数。

样例

样例输入 1

5 8 1 100 10
start 0 0
azhan 10 10
xxgasxx 0 5
bpoint 20 5
end 0 100
start azhan sdf 30
azhan xxgasxx ewfg 20
start end r3tg 200
end azhan 1xq2 70
azhan bpoint gg 10
xxgasxx bpoint kk 30
bpoint end dsg 40
xxgasxx end t_s 100

样例输出 1

162.500

提示

共有十四组数据；

其中三组数据，$n<10,\ m<20,\ k<5$；

另有三组数据没有红绿灯；

所有数据满足 $n \leq 10000,\ m \leq 20000,\ k \leq 10$，加油站数目 $\leq 50$。保证点和边名的长度不大于 $20$，只有大小写字母，数字及下划线 "_" 组成。