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!)$ ~\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)$ ~\mathcal O(n^3)~ complexity, and then answer the questions in $\mathcal O(1)$ ~\mathcal O(1)~.

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

Comments

There are no comments at the moment.