「星間飛行ルートを作ろう！」を解いてみました

CodeIQの「星間飛行ルートを作ろう！ by The Essence of Programming」を解いてみました。
結果は、

でした。 なんとか正解できてほっとしています。
deep星にたどり着いたら、次はdeeper星まで。そしてdeepest星までという感じで、つぎはぎで作ってるので、ちょっと汚いのですが載せておきます。深さ優先探索で解いたのですが、なんでダイクストラ法が頭に浮かばなかったんだろうと反省。ダイクストラ法という名前は知っていても、ここぞというときに使えないといけないですね。

solv.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
require 'net/http'

def solv current, goal
  return if $found_flag
  return if current == 3351698485723 # deeper => deepestで、3351698485723にはまると困るので…
  $route << current
  if current == goal
    $found_flag = true
    return 
  else
    start = $visit_flag[current] ? $visit_flag[current] : 0
    start.upto(Float::INFINITY) {|nth|
      break if $found_flag
      nxt = search(current, nth)
      if $route.include?(nxt)     # 訪問済みの星はスキップ
        next
      elsif nxt == 0              # 次の星がない
        $route.pop
        return
      else
        $visit_flag[current] = nth + 1
        solv(nxt, goal)
      end
    }
  end
end

def search id, nth
  http = Net::HTTP.new('133.242.134.37')
  response, = http.get("/deepest.cgi?id=#{id}&nth=#{nth}")
  response.body.to_i
end

star_id = {
  start: 5426528869786,
  deep: 4363616111476,
  deeper: 5092488161056,
  deepest: 8838746292440
}

$ans = []

puts "start => deep"
$visit_flag = Hash.new
$found_flag = false
$route = []
solv(star_id[:start], star_id[:deep])
$route.pop
$ans << $route

puts "deep => deeper"
$visit_flag = Hash.new
$found_flag = false
$route = []
solv(star_id[:deep], star_id[:deeper])
$route.pop
$ans << $route

puts "deeper => deepest"
$visit_flag = Hash.new
$found_flag = false
$route = []
solv(star_id[:deeper], star_id[:deepest])
$ans << $route

puts $ans.flatten.join(",")