CS
Problems Base course RU

Problem

An electric car in the hills

shortest path weighted graph maps and navigation science and physics

An electric car drives around a hilly city. The height of each intersection is known, as is the length of each street, and each street can be driven both ways. A metre of road costs F units of energy. Climbing a unit of height costs U more, and descending a unit of height gives back D: going downhill the motor charges the battery. So driving along a street of length ℓ with a height difference Δ costs Fℓ + UΔ going up and Fℓ − DΔ going down, and the second number can be negative. A descent never gives back more than the same climb costs: D ≤ U.

The car stands at intersection s. For each intersection in a list, find how much energy it takes to get there by the most economical route. The answer can be negative: then the battery charges on the way.

One of the tests is the streets of Almaty with intersection heights from the SRTM survey and the electric car from the article, in milliwatt-hours and decimetres.

Input

The first line holds the number of intersections n and streets m (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105). The second holds F, U, D (0 ≤ F ≤ 104, 0 ≤ D ≤ U ≤ 104). The third holds the heights of the intersections h1, …, hn, integers from 0 to 105. Then come m lines of three numbers a b ℓ: a street between intersections a and b of length ℓ (1 ≤ ℓ ≤ 104, a ≠ b). Then a line s q and a line of q intersection numbers (1 ≤ q ≤ 105).

Output

q lines: the smallest energy to each intersection in the list, an integer, possibly negative, or “-” if it cannot be reached.

Examples

Example 1

Input
3 2
150 545 294
10 50 90
1 2 100
2 3 100
3 3
1 2 3
Output
6480
3240
0

Example 2

Input
4 4
10 100 90
0 0 100 0
1 2 1000
1 3 5
3 4 5
4 2 5
1 3
2 3 4
Output
1150
10050
1100

Limits

Time · Python
8000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Dijkstra will not do: weights can be negative, and in the second example it would declare the long level road final too early. Bellman–Ford will cope, but on a long road of tens of thousands of intersections it needs as many rounds. Can the weights be made non-negative without changing the answer?

2Hint 2

If p(u) − p(v) is added to the weight of each street u → v, the weight of any route from s to t changes by the same p(s) − p(t). Which p does the problem itself suggest?

3The idea

The potential is height: p(v) = D · hv. Then the reduced weight of a climb by Δ is Fℓ + UΔ − DΔ = Fℓ + (U − D)Δ, and of a descent Fℓ − DΔ + DΔ = Fℓ. Both are non-negative because D ≤ U: this is the claim “height is a potential” from the article. Dijkstra on reduced weights finds the same routes, and the real energy is obtained by the reverse conversion: the number found plus D·(ht − hs).

4Walkthrough

One Dijkstra from s with a binary heap. In the second example the level road 1 → 2 of length 1000 costs 10,000, while the detour over a hill 100 high costs 50 + 100·100 for the climb, 50 − 90·100 for the descent and 50 on the level, 1150 in all. In reduced weights the climb costs 50 + 10·100 = 1050, the descent and the level road 50 each, and Dijkstra honestly finds the detour.

The energy on a route goes up to 1014: Go needs int64.

4+Solution
5Complexity

O((n + m) log n), one Dijkstra. Bellman–Ford costs O(n·m), and on the tenth test, a road of forty thousand intersections whose streets are listed from the far end, it needs forty thousand rounds.

6Common mistakes
  • Dijkstra on the real weights. An intersection is declared final when first taken from the heap, and a descent found later can no longer improve it: the second example.
  • The sign in the reverse conversion. The reduced weight of a route is the energy plus D·hs minus D·ht; to get back to energy, subtract D·hs and add D·ht. The first example, a descent from a hill, shows a sign error at once.
  • A height factor outside the range. Any c from D to U will do: with c = U, for example, a climb costs Fℓ and a descent Fℓ + (U − D)Δ. If c is less than D, steep descents stay negative, and if it is greater than U, steep climbs become negative.
  • Unreachable intersections. A city can come in several pieces: the eighth test.

Algorithms behind it

GRA Algorithm Johnson's algorithm Shortest paths with negative weights: Bellman–Ford potentials, reweighting and Dijkstra from each vertex. O(V·E + V·(V + E) log V) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems
The algorithms catalogue