Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3972
Electric Vehicle Routing

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In recent years, electric vehicles are highly promoted to reduce emissions of greenhouse gas. However, the limited battery capacity of electric vehicles requires visits of recharging stations during the vehicles' tours. In this problem, you are going to plan a route for an electric vehicle to travel from an origin to a destination with the least total cost to charge electricity.

Consider an undirected graph with n nodes and m arcs, denoted by 1, 2, ..., n, where each node represents a location, and each edge (i, j) represent a two-way road connecting location i and location j. There are h recharging stations located at nodes s1, s2, ..., sh, where sp ∈ {1, 2, ..., n} for p = 1, 2, ..., h. A journalist, Kevin, plans to travel from an origin location a to a destination location b. Kevin has an electric vehicle of a battery capacity Q kilowatt-hour (or kWh in short), which can be charged at every recharging station sj (for j = 1, 2, ..., h) at a unit charging cost of 1$ per kWh. For each edge (i, j), the consumption of electricity for the car is dij kWh. Kevin needs to decide a route for his car to travel from origin a to destination b, where the route includes a sequence of locations as well as a plan to charging electricity, so that the car will never be out of electricity. Assuming that the initial charge level of the car is L kWh, your task is to help Kevin to minimize the total charging cost for the car.

Figure 2. An illustrated example with all dij equal to 1, where the best routing of the car is to visit node 1, node 2, node 8 (charging electricity of 3 kWh), node 2, node 3, node 4, and node 5, achieving the minimal total charging cost of 3 dollars.


First line of the input is an integer T indicating the number of test cases. For each case, the first line contains six integers n, m, h, a, b, Q, and L, where 1 ≤ h, a, bn ≤ 1000, 1 ≤ m ≤ 10000, 0 ≤ LQ ≤ 1000000. The second line contains h integers representing locations of recharging stations s1, s2, ..., sh. Each of the following m line contains three integers i, j, and dij, representing an edge (i, j) and its electricity consumption dij.


For each case, if the car cannot arrive at the destination b, then output -1, otherwise, output an integer that equals the minimum total charging cost of electricity for the car to travel from origin a to destination b.

Sample Input

8 7 2 1 5 5 3
7 8
1 2 1
2 3 1
3 4 1
4 5 1
3 6 1
6 7 1
2 8 1
3 2 1 1 3 3 1
1 2 1
2 3 4

Sample Output


Source: ACM Collegiate Programming Contest 2017 (Hong Kong)
Submit    Status