Numbers Quest: Solving Travel Mania
Problem Code: TRAVM
Let's take a look at the approach that can be used to solve the Travel Mania Problem from Numbers Quest Contest.
Approach:
Let’s optimize the very first solution that comes to mind in O ( m * dₘₐₓ ): let’s calculate can [ t ] [ v ] — is it possible to get to the vertex v by going along exactly t edges.
Now, note that the set of edges that we can walk along with changes only m times. Let’s sort the edges in ascending order dᵢ, i.e. for all i dᵢ ≤ dᵢ + 1. Let’s consider the dynamics can [ t ] [ v ] only for t = dᵢ . Suppose we want to go from can [ dᵢ ] to can [ dᵢ + 1 ]. Since the set of edges does not change from time dᵢ to dᵢ + 1, we can raise the adjacency matrix to the power dᵢ + 1 — dᵢ and apply it to can [ dᵢ ].
Suppose we have counted all can [ dᵢ ] [ v ]. Now fix the edge with the maximum dᵢ, along which we go in our shortest path. We know all the vertices at which we can be at the moment dᵢ, then we need to find the shortest path from them to the vertex m along the edges open to us and update the answer. The shortest distance matrix can be calculated by the Floyd–Warshall algorithm, so updating the answer is not difficult.
We got a solution in O ( m * n³ * log ( dₘₐₓ )), which, unfortunately, takes a long time.
Further, it should be noted that the adjacency matrix consists of ones and of zeros, so it can be raised to a degree of compression of the bit O ( n³ /32). This gives a solution in O ( m * n³ * log ( dₘₐₓ ) / 32), which goes smoothly in time.
Time Complexity:
As discussed above after possible optimizations the time complexity for the algorithm becomes O ( m * n³ * log ( dₘₐₓ ) / 32).
Solution:
The solution in c++ :
