The Lost Woods - Travelling Swordsman

The title of this problem is a major hint towards the means of its solution. Even so, some non-trivial reductions must be made to make the problem tractable.

The problem of 'What is the shortest path that can be taken to visit all of the nodes in a graph?' is known as the Travelling Salesman Problem , and it is known to be NP-hard , which doesn't bode well for mazes with up to ten-thousand nodes! Fortunately, only the number of Heart Pieces matters to the TSP part of the solution, and that is bounded in $[2, 10]$ , so an exponential-time solution is quite acceptable.

First, we need to pre-process the maze to produce a graph containing all the data we need to give to the travelling salesman portion. We need to compute the distances between Link and all of the Heart Pieces, as well as between all pairs of Heart Pieces. There are many ways to do this, but the simplest one I can think of, which builds on previous solutions, is to run Dijkstra's Algorithm for each of the important nodes, and save the distances to the other important nodes. This costs $O(W \cdot H \cdot \log(W \cdot H))$ time per iteration, so, letting $N$ be the number of Heart Pieces, it costs that $N$ times, and the resultant data requires $O(N^2)$ space.

Once we have all the distances computed, we can treat the problem as canonical TSP - what is the shortest path, starting from Link, that touches all of the Heart Piece nodes?

If you have a beefy computer and a lot of time to burn, you might get away with the naive solution of trying all permutations of the Heart Piece nodes and figuring out which order is the shortest, in $O(N!)$ time, but this is not necessary. Using Dynamic Programming , the problem can instead be solved in $O(N^2 \cdot 2^N)$ time, via the Held-Karp Algorithm .

To summarize, we first define a sub-problem to solve: Visit $k$ arbitrary Heart Pieces, ending at Heart Piece $h$ , in minimal time. There are $2^N$ subsets of Heart Pieces we could consider, and $O(N)$ ending Heart Pieces to consider, and computing each sub-problem takes $O(N)$ time, given that all previous sub-problems are already solved, hence the $O(N^2 \cdot 2^N)$ runtime.

In Pseudocode:

# Run Dijkstra on each node to generate a map of [node, node] -> distance for the important nodes...

def visitation_state: { set[node] visited_nodes, node last_node }
tsp_cache = map{visitation_state, path_length}

def solve_tsp(vis_state):
  if vis_state in tsp_cache: return tsp_cache[vis_state]
  int val;
  if vis_state.visited_nodes == set[vis_state.last_node]: val = edge_weights[link, vis_state.last_node]
  else:
    val = INT_MAX
    for node in vis_state.visited_nodes: if node != vis_state.last_node:
      len = solve_tsp(visitation_state(vis_state.visited_nodes - set[vis_state.last_node], node))
      len += edge_weights[node, vis_state.last_node]
      if len < val: val = len
  tsp_cache[vis_state] = val
  return val

min = INT_MAX
for node in heart_pieces:
  len = solve_tsp(visitation_state(heart_pieces, node))
  if len < min: min = len
answer += index * min

Click this link to view the scores for each maze from the input in order, sans multiplication by the index. If you were not able to get the right answer, consulting these individual results may help you find the problem (or, if I got something wrong, the bug in my own solution!)