Airports opening
An airline network is built gradually: airports open one at a time, and the flights between them are scheduled in advance. A flight can operate only when both its ends are open, and transfers are possible only at open airports. An analyst wants to watch the network grow: after each airport opens, how many ordered pairs of open airports (a, b), a ≠ b, are already joined by a route, and what is the sum of the lengths of the shortest routes over all such pairs.
Flights are one-way: a flight from a to b does not mean a flight back. There may be several flights of different lengths between one pair of airports. Two tests are the real flights among the 21 airports of the article, with lengths in great-circle kilometres.
Input
The first line holds n and m (1 ≤ n ≤ 150, 0 ≤ m ≤ 25,000): the number of airports and flights. Then come m lines a b w: a flight from a to b of length w (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ w ≤ 10⁶). The last line holds n distinct airport numbers in order of opening.
Output
n lines: after each airport opens, two numbers separated by a space, the number of connected pairs and the sum of the lengths of their shortest routes.
Examples
Example 1
4 4 1 2 5 2 3 4 3 1 2 3 4 7 2 1 4 3
0 0 1 5 1 5 9 67
Example 2
5 5 1 2 10 1 2 3 2 1 3 4 5 1 5 3 6 3 5 4 1 2
0 0 1 6 3 14 3 14 5 20
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 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
You could run Floyd–Warshall over the open airports anew after each opening. This is correct, but what does it cost with 150 airports?
2Hint 2
What does the Floyd–Warshall table know after the step with vertex k? And do the k have to be taken in order of their numbers?
3The idea
Once vertices k1, …, kt have been processed, the cell d[i][j] equals the length of the shortest route from i to j with transfers only at these vertices, for any i and j, open or not. The proof does not use the order of the vertices. Take it to be the order of opening: then after step t transfers are allowed exactly at the open airports, and what remains is to add up the cells between open airports. One pass of Floyd–Warshall instead of n passes.
4Walkthrough
The table d starts as the direct flights; of several flights between a pair, take the shortest. Then for each airport k in order of opening do the ordinary step of the algorithm over all rows and columns: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). The rows of closed airports must be updated too: when airport i opens, its row must already know the routes through everything opened earlier, and there will be no time to recompute it after the fact. After the step, add up the finite d[i][j] over pairs of open i ≠ j.
Why the table has no routes through closed airports: closed airports have not yet been vertex k, and by the invariant the intermediate vertices of all recorded routes are only the processed k. The ends of the route, i and j, are open, because we only sum over them.
This problem is a variant of a well-known one in which vertices are, on the contrary, removed one at a time and the answer is needed before each removal. It is solved the same way by reading the order of removals from the end: the last vertex removed is the first opened.
The sum can be large: up to 150 · 149 pairs with routes of up to 149 · 10⁶, about 3 · 10¹², so Go needs int64.
4+Solution
5Complexity
O(n³) for the steps of the algorithm and O(n³) in total for computing the sums (t² cells at step t), O(n²) memory. Recomputing from scratch after each opening is O(n⁴): with n = 150 that is about 1.3 · 10⁸ steps, too many for Python.
6Common mistakes
- Recomputing from scratch. Correct, but tens of times slower: the fifth test.
- Updating only the open rows. The row of an airport that opens later will miss the steps through the airports opened earlier, and the routes from it will come out longer or go missing.
- Pairs with closed ends. The table knows a route from an open airport to a closed one, but such a pair does not exist yet.
- Several flights between a pair. Taking the last one read rather than the shortest.
- Overflow. The sum does not fit in 32 bits.