
ZOJ Problem Set  3972
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 twoway road connecting location i and location j. There are h recharging stations located at nodes s_{1}, s_{2}, ..., s_{h}, where s_{p} ∈ {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 kilowatthour (or kWh in short), which can be charged at every recharging station s_{j} (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 d_{ij} 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 d_{ij} 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. InputFirst 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, b ≤ n ≤ 1000, 1 ≤ m ≤ 10000, 0 ≤ L ≤ Q ≤ 1000000. The second line contains h integers representing locations of recharging stations s_{1}, s_{2}, ..., s_{h}. Each of the following m line contains three integers i, j, and d_{ij}, representing an edge (i, j) and its electricity consumption d_{ij}. OutputFor 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 Input2 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 2 1 2 1 2 3 4 Sample Output3 1 Source: ACM Collegiate Programming Contest 2017 (Hong Kong) 