Editorial for DMOPC '14 Contest 6 P6 - Trip


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.

Author: Phoenix1369

The given graph is a directed graph with set intervals between each of the nodes. Although every given route will take \le 1440 minutes to get from start to finish, the entire journey from Station U to Station V may span several days.

After processing the input and storing a relation between each of the parent nodes with their children on their respective routes, we can use Dijkstra's Shortest Path Algorithm with a Binary Heap to find the most optimal travel schedule. Be sure to take into consideration the times that will wrap around to the next day on routes that take place during the night!

Time Complexity: \mathcal{O}(Q + S \log S)


Comments

There are no comments at the moment.