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$ $1$ and $n$ $n$ to each word to make the implementation easier.

Notice that the task asks for the length of the shortest path from vertex $a$ $a$ to vertex $b$ $b$ . Therefore, 20 points can be scored using brute force in $\mathcal O(n!)$ $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)$ $O (n^{3})$ complexity, and then answer the questions in $\mathcal O(1)$ $O (1)$ .

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

Comments

There are no comments at the moment.