P3259 [JLOI2014] 路径规划

相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。考虑到实际情况，一辆车加满油能开的时间有限，**为 $limit$**，所以在地图上增加了几个加油站。 地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过 $k$ 个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。（题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油）。 注意： 1. $limit$ 指的是车最多能走多长时间，可以看作车的油箱，是不能叠加的（比如不能连续经过多个加油站后剩余能走的时间 $>limit$）。 2. 与上面类似，一个加油站最多只能加到 $limit$，不能累加。 3. 不管在加油站加多少油，反正加一次耗费的时间都是 $cost$。 4. 经过加油站可以不加油。

第一行输入 $5$ 个整数 $n,m,k,limit,cost$，表示有 $n$ 个点 $m$ 条边，车能开 $limit$ 长的时间，及加油所花时间 $cost$。 接下来 $n$ 行输入每个点信息，包括点的名称（带 `gas` 的为加油站，`start` 为起点，`end` 为终点），及该点是否有红绿灯，用 $a,b$ 表示。（若为 $a=0$ 则表示没有，$a$ 表示红灯长，$b$ 表示绿灯长）。 接下来 $m$ 行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。 保证点和边名的长度不大于 $20$，只有大小写字母，数字及 `_` 组成。

一行输出最少平均花费时长。

共 $14$ 组数据。 - 其中 $3$ 组数据，满足 $1 \le n