pabloskimg's blog

By pabloskimg, history, 4 weeks ago, In English,

I'm trying to solve the problem Routing from ACM ICPC World Final 2006, and I don't have any ideas on how to solve it. Since the number of nodes in the graph is at most 100, I guess a Floyd-Warshall preprocessing should be no problems and could probably help, but after that I really don't have any ideas on what to do next.

Any tips will be appreciated.

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

AFAIK that one is same with problem KAMPANJA.

Solution link.

You can model the problem into a bitonic tour instance, and run a shortest path algorithm on the state graph. Time complexity is about O(n3) ~ O(n4).