Shortest itineraries with no change in common
An agency sells group tours and offers only itineraries with the fewest flights. So that the closure of one airport does not wreck several trips at once, no two groups may change planes at the same airport. How many groups can be sent from s to t at the same time?
An itinerary is a sequence of flights from s to t, with exactly as many flights as the shortest itinerary from s to t. Two itineraries must have no airports in common except s and t. If there is a direct flight from s to t, the shortest itinerary is that flight alone, and the answer is 1. If t cannot be reached, the answer is 0.
Tests 5–7 are the real flight network of the whole world: 3468 airports and 84,869 routes from the Virtual Radar Server callsign database. The seventh test has itineraries from Almaty to the fifty airports with the most routes.
Input
The first line holds the number of airports n and the number of routes m (2 ≤ n ≤ 10⁴, 1 ≤ 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 ≤ 50) and q lines s t (s ≠ t).
Output
q lines: for each query, the largest number of shortest itineraries from s to t no two of which pass through a common airport other than s and t.
Examples
Example 1
5 6 1 2 2 3 1 4 4 3 3 5 2 5 4 1 3 1 5 5 1 2 3
2 1 0 1
Example 2
6 7 1 2 1 3 2 4 2 5 3 4 4 6 5 6 3 1 6 2 6 3 6
2 2 1
Limits
- Time · Python
- 6500 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 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
Which flights can occur in a shortest itinerary at all? Compute the distance from s to each airport and from each airport to t; the second needs a breadth-first search over the flights reversed.
2Hint 2
Keep only such flights and look at the second sample. A greedy pass “found an itinerary, closed its airports, look for the next” finds 1 → 2 → 4 → 6, and the itinerary through 3 runs into the taken airport 4. But the answer is 2. What is the greedy pass missing?
3The idea
A flight u → v lies on a shortest itinerary if ds(u) + 1 + dt(v) = ds(t). Build a network from such flights only: each airport except s and t becomes two vertices, arrival and departure, with an arc of capacity 1 between them, and each flight an arc of capacity 1. The answer is the maximum flow in this network. Any path from s to t along it is shortest, because each arc leads one step further from s, and vertex-disjoint paths are a flow in which at most one unit passes through each airport.
The greedy pass is exactly one phase of Dinic's algorithm: a blocking flow. It need not be maximum: what has been pushed in it cannot be cancelled. The maximum flow comes from continuing the phases on the residual network, where the taken flights and airports have acquired reverse arcs. In the second sample the second phase finds the path 1 → 3 → 4 → (back) 2 → 5 → 6: the itinerary through 2 gives up airport 4 and goes through 5.
4Walkthrough
For each query: two breadth-first searches, from s over the flights and from t over the flights reversed. Keep the airports with ds(v) + dt(v) = ds(t) and the flights between them where ds grows by one. Build the network with split airports and run Dinic with pointers. A direct flight and an unreachable destination are separate cases: 1 and 0.
Reverse arcs in the residual network lead one layer back, so the second and later phases of Dinic look for paths longer than the first. But these are paths in the residual network, not itineraries: the final flow goes only along arcs of the original network, each of which leads one step forward, and it decomposes into itineraries of the shortest length.
4+Solution
5Complexity
The network of split airports is a unit network: many arcs lead into an arrival but one leaves it, many leave a departure but one enters it. By the theorem on unit networks there are at most 2√V + 1 phases, each in O(E), so per query O(n + m) for the breadth-first searches and O(E√V) for the flow, where V and E are the size of the network of shortest flights. On the world network it is usually small; the eighth test has 10,000 airports in eight layers, and 1244 itineraries.
6Common mistakes
- One phase. A greedy pass through the layers without reverse arcs is
wrong.py. On fifty random pairs of the world's airports it is wrong twice, on the chosen pairs of the sixth test always, and in the tenth test, made of fifteen hundred traps like the second sample, it finds 1500 itineraries instead of 3000. - Flow over the whole network. If flights outside shortest itineraries are not discarded, the flow counts longer itineraries too. In the first sample the shortest itinerary from 1 to 5 is only 1 → 2 → 5, while with the itinerary 1 → 4 → 3 → 5 the answer would be 2.
- Without splitting the airports. Capacity 1 on the flights alone forbids common flights, but not common airports: two itineraries could arrive at one airport by different flights and leave it by different ones.