A Journey to Greece
This problem gives us a graph and asks us whether we can visit a certain subset of nodes in a given time. The caveats are
- there is a given time we will spend at each node
- there is a transit time between nodes
- he may travel between any pair of nodes at most once at a fixed cost
We have 2*10^4 nodes, 15 places to visit, and 10^5 edges.
The first simplification is that we only have FIFTEEN places to visit, but 20k nodes. Since only 15 places are interesting, we can calculate the minimum time from any of these nodes to any other by running dijkstra from each node. This takes 15 * (120klog20k). This is plenty fast enough. Now we have 15 nodes, and are asked for the minimum circuit time. If we ignore the third stipulation above, this is simple travelling salesman. We figured it must be some sort of brute force because N=15.
Ignoring the third case above, Simply iterating over all 15! paths is too slow. We notice, however, that if we are located at a given node, and the given set of nodes we have ALREADY visited is fixed, the solution for the remaining nodes does not depend on the previous path. This leads to a DP state:
-set of nodes already visited (2^15 possibilities) -which node we are at (15 possibilities)
and we store in the table the minimum time it took to reach this state.
We initialize the minimum time to be at athens without visiting any other cities at 0, and the rest of the elements to inf. At every element in our DP array, we iterate over all elements possible next cities to visit, and replace the value in the appropriate next cell if it is a faster way to reach that state.
Without the taxi, the state space is 15 locations * 2^15 cities visited possibilites = 500k. Even with a factor of 15 for evaluating every possible city, this is only 7 million.
Incorporating the taxi is now trivial. We simply add one further dimension to our array, indicating whether we've already used the taxi or not. In our iteration step, we have to simulate taking the taxi to every possible next city as well as going the 'normal' way. This increases our runtime to ~30 million, which is still plenty fast.