Changes of plane
A ticket search service answers the question “how many flights does it take to get from airport s to airport t”. The timetable does not matter, only the routes do: a flight from a to b does not mean there is a flight back. There are many queries, and each must be answered quickly.
Tests 3–5 are the real air network of the whole world: 3468 airports and 84,869 routes from the call-sign database of Virtual Radar Server. The fourth test has all routes from and to Almaty.
Input
The first line holds the number of airports n and the number of routes m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 10⁵). Then m lines a b: there is a flight from a to b (1 ≤ a, b ≤ n, a ≠ b, no repeats). Then the number of queries q (1 ≤ q ≤ 10⁴) and q lines s t.
Output
q lines: the smallest number of flights from s to t, or -1 if it is impossible to fly there. If s = t, the answer is 0.
Examples
Example 1
6 8 1 2 1 4 2 3 3 5 4 2 4 5 5 3 5 6 4 1 6 1 5 6 1 3 3
3 2 -1 0
Example 2
5 6 1 2 2 3 3 1 3 4 4 3 2 5 5 1 4 4 1 5 1 1 5 5 5
3 2 -1 2 0
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 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
One query is an ordinary breadth-first search. Count how many airports it will mark on the world network, if you can fly from anywhere to anywhere in three or four flights. And how many queries are there?
2Hint 2
Send two waves: from s along the routes and from t along the routes backwards. How many airports will each mark if they only need to go two flights each? And when can you stop? Look at the first sample.
3The idea
Bidirectional breadth-first search in which the waves grow by whole layers, and each time the one whose current layer is smaller grows. The very first touch, a flight from a new airport of one wave to an airport already marked by the other, gives the answer. In a network where each flight multiplies the reach, two waves of depth d/2 mark on the order of the square root of what one wave of depth d marks.
4Walkthrough
Keep two adjacency lists: out[a], where you can fly from a, and into[b], where you can fly into b from. The wave from s goes along out, the wave from t along into. Each wave has a dictionary “airport → depth” and a current layer. Choose the wave with the smaller layer and go through all of its layer; if a neighbour is already marked by the other wave, the answer is the depth of the current layer + 1 + the neighbour's depth in the other wave.
Why the first touch is already the shortest. Let the wave from s have gone through the layers to depth ks, the wave from t to kt, and let there have been no touches yet. Then the marked sets do not intersect: there is no airport at most ks flights from s and at most kt flights from t. On a shortest route of length L the airport after ks flights is L − ks flights from t, so L > ks + kt. And a touch while going through the layer of depth ks gives a route of length ks + 1 + (the depth in the other wave) ≤ ks + 1 + kt. That is the minimum.
Dictionaries instead of arrays of length n: a query touches a hundred or two airports, and clearing arrays of 10⁴ elements after each of 10⁴ queries is 10⁸ extra writes. In Go, instead of dictionaries, shared arrays with a “query number”: an airport counts as marked only if the number of the current query is written in it.
4+Solution
5Complexity
In the worst case, a chain without branches as in the sixth test, a query costs O(n + m), like one wave. On the air network a query marks a hundred and fifty airports on average instead of fifteen hundred for one wave and stops having looked at only part of their flights: in Python the reference answers queries about the world network tens of times faster than one wave, and one wave does not fit in the time limit.
6Common mistakes
- Airports one at a time, from two queues in turn. The most common mistake: the waves alternate not by layers but by single airports, and the search stops at the first touch. Then a wave's queue holds airports of two neighbouring layers, and a touch can come through the deeper one. In the first sample the answer for 1 → 6 comes out 4 instead of 3: the wave from 6, processing airport 5, first sees airport 3, which the wave from 1 reached only with its second flight, and stops without looking at airport 4, which is one flight from 1. This is
wrong.py; on the world network it is off by one in about one query in six. - The second wave along the routes “forward”. A flight a → b does not mean a flight b → a. In the second sample you cannot fly anywhere from airport 5, though you can fly into it.
- One wave. The answers are right, but on the world network a breadth-first search to the finish marks fifteen hundred airports on average, and ten thousand queries do not fit in the time.