Maxon5's blog

By Maxon5, history, 11 months ago, In English,

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?

  • Vote: I like it  
  • +10
  • Vote: I do not like it