Needed help for graph theory problem from NEERC Moscow Subregional of 2011

Revision en1, by Maxon5, 2017-11-19 22:06:18

Can someone please give any idea about how to solve problem G.Tourist of this set?

The problem basically gives you a directed graph, a source, a destination and a list of interesting nodes. You have to start from the source and reach the destination and visit all the interesting nodes on your path. You are allowed to visit a node multiple times but you cannot use more than n^2 nodes in your path. You have to print the path or say it is not possible. Number of nodes is 2000 and number of edges can be 2000*2000.

I have a O(V*E) solution for the problem. But that is not going to be enough. Can someone give any better idea?

Tags #graph


  Rev. Lang. By When Δ Comment
en1 English Maxon5 2017-11-19 22:06:18 744 Initial revision (published)