Editorial for COCI '20 Contest 6 #2 Alias

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We can think of Rafael's database as a directed weighted graph. Since vertices are words, we need to first assign a unique integer between 1 and n to each word to make the implementation easier.

Notice that the task asks for the length of the shortest path from vertex a to vertex b. Therefore, 20 points can be scored using brute force in \mathcal O(n!) complexity. For additional 20 points, we can use the Floyd-Warshall algorithm to calculate distances between every two points in \mathcal O(n^3) complexity, and then answer the questions in \mathcal O(1).

For all points, we can use Dijkstra's algorithm for each question, which has \mathcal O(m \log n) complexity. The total complexity of our solution is then \mathcal O(qm \log n).


There are no comments at the moment.