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

Notice that the task asks for the length of the shortest path from vertex to vertex . Therefore, 20 points can be scored using brute force in complexity. For additional 20 points, we can use the Floyd-Warshall algorithm to calculate distances between every two points in complexity, and then answer the questions in .

For all points, we can use Dijkstra's algorithm for each question, which has complexity. The total complexity of our solution is then .

## Comments