#P3627. [JLOI2014]路径规划
[JLOI2014]路径规划
[JLOI2014] 路径规划
题目描述
地图上有若干路口和双向道路。汽车从起点出发时油箱已满,续航为 。某些路口设有加油站,另一些路口设有红绿灯。请找出一条从起点到终点的路线,使途中经过的红绿灯次数不超过 ,且平均总耗时最少。
一个红绿灯循环依次亮 时间的红灯和 时间的绿灯。按在一个周期内均匀到达计算平均等待时间。平均行驶耗时包括道路行驶时间和沿途的平均等灯时间。每段从满油出发到下次加油或抵达终点的平均行驶耗时不能超过 。
在加油站可自行选择是否加油。每加一次油耗时 ,最多把油箱恢复到满油的状态,多次加油也不会使续航超过 。加油时间计入总耗时。起点、终点和加油站均没有红绿灯。
输入格式
第一行五个整数 ,依次表示路口数、道路数、至多经过的红绿灯次数、满油续航及一次加油所需时间。
接下来 行,每行给出一个路口的名称与两个整数 。名称为 start 和 end 的路口分别是起点和终点,名称含有 gas 的路口是加油站。 表示该路口没有红绿灯,其余情况下 分别表示红灯和绿灯的持续时间。
接下来 行,每行给出一条双向道路两端的路口名称、道路名称及通过该道路所需时间。
路口和道路名称都由大小写英文字母、数字、下划线构成,长度不超过 。
输出格式
输出一行,表示最少平均总耗时,保留三位小数。本题库约定,无可行路线时输出 -1.000。
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
162.500
数据范围
,,,加油站不超过 个。
共 个测试情形。原题记载部分小数据满足 、、,另有三组没有红绿灯。