Solving a Number-Hopper Maze My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:



The idea is to start from x and reach o via the normal rules.  Additionally, you can "hop" from any integer $a$ to any other integer $b$, but you must pay $|a-b|$ dollars for the privilege.  The goal is to solve the maze for the least cost.  In the example above, we could go from x to o via x-14-18-27-28-o at cost 5, but it's cheaper to go x-13-11-9-8-29-28-o for only 4.

So here is my question: what is the best solution (in terms of asymptotic running time) you can think of for solving this?  You may make any reasonable assumptions about the input format.

Note: I am using the "puzzles" tag here because I have an $O(n^2)$ answer in mind, but I'm not sure it's optimal and would like to see if someone else can improve my solution.  (Here $n$ is the number of integers in the maze.)
You can solve this in $O(n\log n)$ time using a variation of Dijkstra's algorithm. We can get away with not performing all distance updates when we visit a new node. If we visit a node $y$, we need only to update the distances of everything walkable from $y$ to 0, and to update the distances to the two nodes $y_-$ and $y_+$ with the closest values to $y$ less and greater than $y$ which have not been picked yet.

These updates are sufficient to keep the heap returning the minimum element because any closest node you jump to must have been numerically just above or just below an already visited node.

Each node gets updated to 0 at most once (if we pop out all zero distance nodes from the queue to avoid quadratic behavior), and each time we add a node, we only do O(1) other updates. Finding the values $y_-$ and $y_+$ can be done in linear time if we also keep an ordered doubly-linked list of all the nodes, sorted by their integer values. Building this doubly-linked list takes $O(n \log n)$ time, and finally the $O(n)$ updates to and pops from the heap take $O(n \log n)$ time, for a total runtime of $O(n \log n)$