Queries over the tiers

shortest path precomputation heap weighted graph maps and navigation

The navigator's precomputation has already been done: the crossroads are ordered by importance, and shortcuts have been added to the streets, edges that replace paths through unimportant crossroads. Each edge of the resulting graph is written from the bottom up: from the less important end to the more important one. Of course, an edge can be driven in both directions.

The graph was built by contraction, so it has the main property of a hierarchy: for any two crossroads s and t, among the shortest paths between them there is one that first only climbs to more important crossroads and then only descends. Answer queries about shortest distances, faster than an ordinary Dijkstra over the whole graph.

Tests 3 and 4 are the hierarchy of the streets of central Almaty built by the precomputation from the article: 7909 crossroads, 10,389 streets and 12,545 shortcuts.

Input

The first line holds the number of crossroads n and the number of hierarchy edges m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 3·10⁴). Then m lines a b w: an edge of length w between a and b, where a is less important than b (1 ≤ w ≤ 10⁷). Then the number of queries q (1 ≤ q ≤ 5000) and q lines s t.

Output

q lines: the length of the shortest path from s to t, or -1 if there is no path.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 8000 ms
Time · Go: 2500 ms
Memory: 256 MB
Judging: 8 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

An ordinary Dijkstra over the whole graph (edges in both directions) gives correct answers, but on a city of eight thousand crossroads it looks at four thousand per query on average. How can you use the fact that the shortest path can be sought in the form “up, then down”?

2Hint 2

The climb from s is Dijkstra from s only along edges going upward. The descent to t, read backwards, is also a climb, only from t. Two waves, and both use the same “upward” edges.

3Hint 3

When should the waves stop? Check the rule from bidirectional search, “the sum of the two smallest keys is no less than the best path”, on the first sample.

4The idea

Run two Dijkstras along upward edges, from s and from t, in turn, each time the one whose smallest key is smaller. When a wave takes a vertex that has a label from the other wave, this vertex is “at the top” of some up-down path, and the best path best is updated. A wave ends when its smallest key is no less than best: any up-down path shorter than best climbs from that wave's end to a height of less than best, so this wave has already taken its top vertex.

5Walkthrough

Keep only the “upward” edges: up[a] is a list of pairs (b, w). For each query, two heaps, two distance dictionaries and two sets of processed vertices. Choose the side with the smaller heap top; skip stale entries; if the key is no less than best, empty that heap. Otherwise the vertex is processed: if it has a label from the other side, try to improve best; then ordinary relaxation along up.

Why the answer is right. Let P be a shortest “up, then down” path with top vertex x; its climb from s to x has length a, the climb from t to x length b, and a + b = δ(s, t). While best > δ, the keys of the wave from s smaller than a < best will still be taken, and Dijkstra along upward edges takes x with a distance of at most a; likewise for the wave from t. When the second of the waves takes x, best becomes at most a + b. And it cannot be more than δ, as it is the length of a real path. More in the article on contraction hierarchies.

5+Solution

6Complexity

Each query is two small Dijkstras over the top of the hierarchy: on the streets of Almaty they look at about 120 crossroads on average, instead of 4000 for an ordinary Dijkstra. In the worst case it is O((n + m) log n) per query, as for Dijkstra, but on graphs where the hierarchy came out well this is rare.

7Common mistakes

The bidirectional Dijkstra stop. The rule “the sum of the smallest keys ≥ best” relies on each wave being an honest Dijkstra over one and the same graph, with keys that are real distances from its end. An upward wave does not see the whole graph, and its keys are lengths of upward paths, not of shortest paths. In the first sample the wave from 3 climbs straight to vertex 4 (key 7), the wave from 1 to 4 (key 2), and the sum 9 updates best = 9. The keys 7 and 5 already add up to more than 9, and the rule stops the search, although the wave from 1 has not yet taken vertex 3, through which the path is only 5. This is wrong.py; on the streets of Almaty it is wrong on about half of the queries.
Stopping at the first meeting. The first vertex taken by both waves is usually not the top of a shortest path: even more mistakes.
Dijkstra over the whole graph. The answers are right, but on thousands of queries to the city it is tens of times slower, and Python does not fit in the time.

Algorithms behind it

GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem 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