By regarding towns as vertices, and roads etc. as edges, this problem can be regarded as a shortest path problem.

If there are no additions of roads and airports

The problem can be solved in \(O(N^3+Q)\) time by precomputing shortest distance between all pairs of vertices with the Floyd-Warshall algorithm.

If there are only road additions

Precompute the shortest distance between all pairs of vertices.

When an edge between \(x\) and \(y\) of cost \(t\) is added, the shortest distance between \(i\) and \(j\) becomes one of the following:

• travel from \(i\) to \(x\), then to \(y\) via the new edge, and then reach \(j\);
• travel from \(i\) to \(y\), then to \(x\) via the new edge, and then reach \(j\);
• remains unchanged.

This can be computed in \(\Theta(1)\) time for each \((i,j)\), so the shortest distance between all pairs can be recalculated in \(\Theta(N^2)\) time. Hence, the problem can be solved in a total of \(O(N^3+N^2Q)\) time.

The original problem

If we directly connect towns with airports, it can result in at most \(\Theta(N^2)\) routes. If we add edges between all towns with airports every time an airport is built and recalculate the shortest distances in a total of \(\Theta(N^2)\) time, the total time complexity will be \(\Theta(N^4+N^2Q)\), which is difficult to finish within the execution time limit. The situation is the same even if we add edges at once and perform Floyd-Warshall algorithm again.

Instead of directly connecting towns with airports, let us define a new vertex representing “the sky,” and consider as follows:

• One can travel from any town with an airport to “the sky” in \(T\) hours.
• One can travel from “the sky” to any town with an airport in \(0\) hours.

Now, only two new edges are required to be added on airport construction, and the shortest distances between all pairs of vertices can be done in \(\Theta(N^2)\) time. In total, the problem can be solved in \(O(N^3+N^2Q)\) time.