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?