Of the Children
BFS state explotion. State would have to be list of cities visited, city we're at, and amount of money we have. Then binary search across starting $ to find the minimum needed.
Runtime log(10,000) * 24 * 2^24 * 10000 = ~10^13
eugh.
BUT...it's a bit smaller than that....there are only 23 cities max, and the start and end are fixed...which brings the DP bit down to 21
21*2^21*10000*log(10000) = ~10^12
we're getting closer....but not good enough
what if we BFS our paths, and keep track of the most in debt we go along the journey, and that's the amount we'd need to start with
21*2^21*10000 = 440 billion....smaller
Hmmm....what to do....
AH! Process the states in number of cities visited total order!
- start with 0 cities visited and loop to all cities visited
- loop over all combinations of cities previously visited
- each one stores the minimum debt needed to get to that