Shortest Path with Fuel and Traffic Light Constraints

You are given a map represented as an undirected graph with n nodes and m edges. Each node represents an intersection which may have a traffic light. Some special nodes (start, destination and fuel stations) are guaranteed not to have traffic lights. A vehicle, starting with a full tank that lasts for limit units of time, needs to travel from a given start node to a destination node. When traversing an edge, the travel time is deducted from the available fuel. At any fuel station, you can choose to refuel (resetting the fuel to limit) at an extra time cost of cost (this cost is incurred every time you refuel regardless of the amount of fuel added). Note that the fuel cannot be accumulated: even if you visit multiple fuel stations in a row, your fuel is always reset to at most limit.

Furthermore, you want your route to pass through no more than k intersections with traffic lights. For every intersection that has a traffic light (except the start, destination, and fuel stations), the count increases by one when you arrive there.

Your task is to compute the minimum total time needed to travel from the start to the destination under the given constraints. If no such route exists, output -1.

Note:

• The available fuel is represented by limit. It denotes the maximum travel time the car can go on a full tank and cannot exceed this amount.
• At a fuel station, refueling resets the fuel to exactly limit and incurs an additional time of cost, even if you do not use the full capacity.
• You may choose not to refuel at a fuel station.

inputFormat

The input is given as follows:

n m limit cost k
s t
TL[1] TL[2] ... TL[n]
f
f1 f2 ... ff
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n and m are the number of nodes and edges respectively. Nodes are numbered from 1 to n.
• limit is the maximum travel time (fuel capacity) on a full tank.
• cost is the extra time cost incurred when refueling at a fuel station.
• k is the maximum number of intersections with traffic lights you are allowed to pass through.
• s and t are the start and destination node indices.
• The next line contains n integers (each 0 or 1) representing whether node i has a traffic light (1 means it has a traffic light, 0 means it does not). It is guaranteed that the start node s, destination node t, and any fuel station have a 0.
• f denotes the number of fuel stations.
• The following line contains f space-separated integers indicating the node indices of the fuel stations.
• Then follow m lines, each containing three integers u v w representing a bidirectional road connecting nodes u and v with travel time w.

You may assume that all numbers are positive integers.

outputFormat

Output a single integer: the minimum total time needed to travel from s to t while passing through at most k intersections with traffic lights. If no valid route exists, output -1.

sample

5 6 10 5 2
1 5
0 1 0 1 0
1
3
1 2 3
2 3 4
3 4 3
4 5 4
1 4 10
2 5 10

19