Resolvendo um labirinto com funil de números

Meu filho de 8 anos se cansou de criar labirintos convencionais e passou a criar variantes que se parecem com isso:

A idéia é começar de x e alcançar o através das regras normais. Além disso, você pode "saltar" de qualquer número inteiro para qualquer outro número inteiro b , mas você deve pagar | a - b | dólares pelo privilégio. O objetivo é resolver o labirinto pelo menor custo. No exemplo acima, poderíamos ir de x para o via x-14-18-27-28-o no custo 5, mas é mais barato ir para x-13-11-9-8-29-28-o apenas 4)$a$$b$$|a-b|$

Então, aqui está a minha pergunta: qual é a melhor solução (em termos de tempo de execução assintótica) que você pode pensar para resolver isso? Você pode fazer suposições razoáveis ​​sobre o formato de entrada.

Nota: Estou usando a tag "puzzles" aqui porque tenho uma resposta em mente, mas não tenho certeza se é o ideal e gostaria de ver se alguém pode melhorar minha solução. (Aqui n é o número de números inteiros no labirinto.)$O(n^2)$$n$

$O(n\log n)$$y$$y$$y_-$$y_+$$y$$y$

Essas atualizações são suficientes para manter a pilha retornando o elemento mínimo porque qualquer nó mais próximo para o qual você salta deve estar numericamente logo acima ou logo abaixo de um nó já visitado.

$y_-$$y_+$$O(n \log n)$$O(n)$$O(n \log n)$$O(n \log n)$

$O(n^2)$

Parece natural converter isso no problema de caminho mais curto com um nó inicial especial (x) e um nó final (0). Também haveria um outro nó para cada um dos números. Tanto x como 0 têm arestas de peso 0 para todos os nós numéricos que são alcançáveis ​​no labirinto. Todos os nós numéricos são conectados com o peso 0 (se os números forem acessíveis pelo labirinto) ou com a diferença entre os números (se não for possível com o labirinto).

$O(n^2)$$n^2$$O(n^2)$