Description

Most people have used the path planning feature on maps: as long as you enter the start and end, it can find an optimal route. Now you are given information about a map; please find the optimal path (i.e., the shortest path). Considering reality, a car with a full tank can run for a limited time, namely $limit$, so several gas stations are added on the map.

The map consists of vertices and bidirectional edges. Each vertex represents an intersection and may be a gas station or the start/end. Some intersections also have traffic lights. Since passing too many traffic lights is annoying, please find the minimal average time needed to travel from the start to the end while passing through no more than $k$ traffic lights. It is guaranteed that the start, the end, and gas stations have no traffic lights. (The problem does not consider whether refueling is possible in the worst case; it only considers whether, under average travel time, the car can reach a gas station to refuel.)

Note:

1. $limit$ is the maximum time the car can drive and can be viewed as the fuel tank; it cannot be accumulated (for example, after passing multiple gas stations in a row, the remaining drivable time cannot exceed $limit$).
2. Similarly, a single refuel can only fill up to $limit$ and cannot be accumulated.
3. No matter how much fuel is added at a gas station, the time cost for one refuel is always $cost$.
4. Passing a gas station does not require refueling.

Description

Input Format

The first line contains $5$ integers $n, m, k, limit, cost$, meaning there are $n$ vertices and $m$ edges, the car can run for time $limit$, and refueling costs time $cost$.

The next $n$ lines describe each vertex, including the vertex name (names containing gas are gas stations, start is the start, and end is the destination) and whether the vertex has a traffic light, represented by $a, b$. (If $a = 0$, it means there is no traffic light; otherwise, $a$ is the red duration and $b$ is the green duration.)

The next $m$ lines describe each edge, including the edge’s start, end, edge name, and the time to traverse this edge.

The lengths of vertex and edge names are no more than $20$ and consist only of letters, digits, and _.

Output Format

Output one line: the minimal average time spent.

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

Hint

There are $14$ sets of testdata.

• Among them, $3$ sets satisfy $1 \le n < 10$, $1 \le m < 20$, $1 \le k < 5$.
• Another $3$ sets have no traffic lights.

Constraints: For all data, $1 \le n \le 10000$, $1 \le m \le 20000$, $1 \le k \le 10$, and the number of gas stations $\le 50$.

Translated by ChatGPT 5