A stop on the way

shortest path weighted graph heap maps and navigation binary search

A courier takes an order from point A to point B through the centre of Almaty. On the way they need to drop in at one more place, for coffee, a pharmacy, a cash machine, and are willing to drive at most D metres longer than the shortest route. At how many crossroads can such a route pass? A crossroads v fits if the shortest path from A to v and then from v to B is at most D longer than the shortest path from A to B.

Some streets are one-way. The courier is honest and drives only by the rules, including on the way from v to B. The answer is needed for many values of D at once: the courier has not yet decided how much delay they will accept.

Tests 3–5 are the real streets of central Almaty with one-way traffic as marked in OpenStreetMap. The rest are made up.

Input

The first line holds the number of crossroads n and the number of street segments m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2·10⁵). Then m lines a b w: the segment can be driven from crossroads a to crossroads b, and its length is w metres (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10⁴). A two-way street is written as two lines. Then a line with the numbers A and B (A and B may coincide; B can be reached from A). Then the number q (1 ≤ q ≤ 10⁵) and a line of q numbers D (0 ≤ D ≤ 10⁹).

Output

One line of q numbers separated by spaces: for each D in input order, how many crossroads fit. A and B themselves, like all crossroads of a shortest route, fit for any D. A crossroads from which B cannot be reached never fits.

Examples

Example 1

Input

6 10
1 2 100
2 1 100
2 3 100
3 2 100
3 6 100
1 4 150
4 5 100
5 4 100
5 6 120
6 5 40
1 6
4
0 50 70 100

Output

4 4 6 6

Example 2

Input

Output

4 4 4

Limits

Time · Python: 5000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 9 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

For each crossroads v you need two numbers: how far it is from A to v and how far from v to B. One Dijkstra gives the first for all v at once. How can one run give the second for all v?

2Hint 2

A path from v to B is a path from B to v if you drive along all the streets backwards. Along which streets must the wave from B go then?

3Hint 3

Once the detour is known for every crossroads, each query must be answered with how many detours are at most D. Going through all crossroads for each of 10⁵ queries takes too long.

4The idea

These are the two complete waves of bidirectional search: the wave from A along the streets in their direction gives d(A, v), the wave from B along the streets against their direction gives d(v, B). The detour through v equals d(A, v) + d(v, B) − d(A, B). It is not negative: a path through v is a path from A to B too. Sort the detours and for each query find by binary search how many of them are at most D.

5Walkthrough

Read the segments and build two adjacency lists: forward[a] with the arcs a → b and backward[b] with the same arcs reversed, b → a. Dijkstra over forward from A and over backward from B. A crossroads that cannot be reached from A, or from which B cannot be reached, is skipped. The other detours are sorted, and the answer to a query is bisect_right(extra, D): the number of detours not exceeding D.

The set of crossroads that fit is an “ellipse” in the road metric: the points whose sum of distances to A and to B is at most d(A, B) + D. On a plane this would be a real ellipse with foci A and B; with one-way streets it loses its symmetry, because the way to B and the way back are different paths.

5+Solution

6Complexity

Two Dijkstras are O((n + m) log n), sorting O(n log n), and each query O(log n). The naive answer to a query by going through all crossroads costs O(nq) = 10¹⁰ operations in the worst case.

7Common mistakes

The second wave along the streets in their direction. This gives the distance from B to v, not from v to B. On a map with two-way streets they are the same, and the mistake is invisible, but one-way traffic gives it away already on the first sample: the segment 3 → 6 leads into B only one way, and the wave from B along the streets “forward” will not reach crossroads 1, 2 and 3 at all. This is wrong.py.
Crossroads where one of the distances is infinite. In Python an infinite float added to a number honestly fails the check, but if you store −1 as “unreachable” and forget to check it, the detour comes out negative and gets into the answer for D = 0. In the second sample there is a dead end at 4: you can drive in, but not out.
32-bit numbers. A distance can reach (n − 1) · 10⁴ ≈ 10⁹, and the sum of two distances 2·10⁹: in languages with a 32-bit int this is right at the limit 2³¹ − 1 = 2,147,483,647, and any extra term will cross it. In Python and in Go, where int is 64-bit, there is no need to think about it.

Algorithms behind it

GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((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