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.
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).
I have tried to get the problem accepted most of the day. But I can not get it correct. I have written different solutions, but they all the same wrong result. I have tried writing with and without a blank line after each test case. I have also tried writing "Impossible" instead of "IMPOSSIBLE" because that is what the solution on uDebug does. Any help is appreciated.
Here is my python solution, which gets TLE(the TLE is not the problem, because it gets the same result as the c++ solution): https://pastebin.com/gJB8a2v2
This is my brute force: https://pastebin.com/ZdavPK4M
I use this script to generate data: https://pastebin.com/bYYryFAb
This is a modification of the c++ solution ko_osaga posted: https://pastebin.com/D5U83tdm
I have tried submitting here: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=35&page=show_problem&category=0&problem=3498&mosmsg=Submission+received+with+ID+23069820
and here: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1571&mosmsg=Submission+received+with+ID+2527676
I have tried testing my solution here: https://www.udebug.com/LA/3570 and here https://www.udebug.com/UVa/1057