最短経路

class TimeInfo
  attr_accessor :time, :decision, :parent_idx
  def initialize(time, decision, parent_idx)
    @time = time
    @decision = decision
    @parent_idx = parent_idx
  end
end

class Tokyu
  @@stations = ["yokohama","musashikosugi","shinagawa","shibuya","shinbashi","tameikesannou", "saihate1", "saihate2"]
  @@adjacency = [
    [0,12,28,0,0,0,0,0],
    [12,0,10,13,0,0,0,0],
    [28,10,0,11,7,0,0,0],
    [0,13,11,0,0,9,0,0],
    [0,0,7,0,0,4,0,0],
    [0,0,0,9,4,0,0,0],
    [0,0,0,0,0,0,0,90],
    [0,0,0,0,0,0,90,0],
  ]
  #路線状態表示用
  def self.debug
    @@stations.each_with_index do |station, idx|
      p station
        @@adjacency[idx].each_with_index do |time, jdx|
          p "->#{@@stations[jdx]} : #{time}" if time != 0
        end
      p "--------"
    end
  end

  #結果表示用
  def self.show(result)
    timeinfo = result[:timeinfo]
    goal = result[:goal]
    p timeinfo[goal].time
    tmp = timeinfo[goal]
    while tmp.parent_idx != -1
      p " <- #{@@stations[tmp.parent_idx]} <-"
      tmp = timeinfo[tmp.parent_idx]
    end
  end

  #隣り合う駅を取得
  def self.next_trains_idx(idx)
    result = []
    @@adjacency[idx].each_with_index do |time, jdx|
      result << jdx if time != 0
    end
    result
  end
  def self.min_way(start_station, end_station)
    start = @@stations.index(start_station) ; goal = @@stations.index(end_station)
    timeinfo = []
    @@stations.length.times do |i|
      timeinfo << TimeInfo.new(-1, 0, -1)
    end
    timeinfo[start] =  TimeInfo.new(0, 1, -1)
    tmp = _min(timeinfo, goal)
    raise "tadoritukenai" if tmp[goal].time == -1
    result = {}
    result[:timeinfo] = tmp
    result[:goal] = goal
    result
  end

  def self._min(timeinfo, goal)
    return timeinfo if timeinfo[goal].decision == 1
    ok = 0
    timeinfo.each{|info| ok += info.decision}
    return if ok >= timeinfo.length
    timeinfo.each_with_index do |obj, i|
      if obj.decision == 1
        next_trains_idx(i).each do |j|
          if timeinfo[j].decision == 0
            if (timeinfo[j].time == -1 || timeinfo[j].time > timeinfo[i].time + @@adjacency[i][j])
              timeinfo[j].time =timeinfo[i].time + @@adjacency[i][j]
              timeinfo[j].parent_idx = i
            end
            next_trains_idx(j).each do |k|
              if timeinfo[k].decision == 0
                if (timeinfo[k].time == -1 || timeinfo[k].time > timeinfo[j].time + @@adjacency[j][k])
                  timeinfo[k].time =timeinfo[j].time + @@adjacency[j][k]
                  timeinfo[k].parent_idx = j
                end
              end
            end
            #自分から延びる全ての辺を処理すれば確定となる
            timeinfo[j].decision = 1
            _min(timeinfo, goal)
          end
        end
      end
    end
    timeinfo
  end
end

#路線図の状態
#Tokyu.debug

#1番目の駅に隣り合う駅を取得
#p Tokyu.next_trains_idx(1)

answer = Tokyu.min_way("shibuya","yokohama")
Tokyu.show(answer)

#参考
p answer