A91378.「JLOI2014」路径规划

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

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

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过 $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$ 行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。

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

共有十四组数据；
其中三组数据，$n<10,\ m<20,\ k<5$ ；
另有三组数据没有红绿灯；
所有数据满足 $n \leq 10000,\ m \leq 20000,\ k \leq 10$，加油站数目$\leq 50$。保证点和边名的长度不大于$20$，只有大小写字母，数字及下划线 "_" 组成。