yukicoder No.17 2つの地点に泊まりたい

問題

No.17 2つの地点に泊まりたい - yukicoder
N個のノードとM個の枝の無向グラフが与えられる。
枝の移動コストとノードの滞在コストが設定されているので
ノード0からスタートし、2つのノードに滞在したうえでノードN-1に向かう最小コストを求める。
ノードは滞在せずに通ることもできる。

解法

ワーシャルフロイド

まずワーシャルフロイドで各ノード間の距離を求める。
滞在する2つのノードの順序を全探索し、最短距離を求める。
これが想定解だった。$O(N^3)$

ダイクストラ

ノード×これまで滞在したノード　を頂点にしたダイクストラ。
自分はこれで書いてしまったが、オーダーいくつになるのかよくわからない。
ダイクストラは$O( (頂点数+枝数)\log(頂点数) )$らしいので
$O( N\times _nC_2\times \log(N\times _nC_2))\simeq O(N^3\times \log(N^3))$?ってことかな。
わざわざ複雑なことをして遅い解法にしてしまったようだ。

#7962 No.17 2つの地点に泊まりたい - yukicoder

s=(1..n=gets.to_i).map{gets.to_i}
c=(1..n).map{{}}
gets.to_i.times{
  a,b,d=gets.split.map(&:to_i)
  c[a][b]=c[b][a]=d
}
q=[[0,0,[0,n-1]],[1e9]]
gone={}
while q[0]&&(q[0][1]<n-1||q[0][2].size<4)
  cost,current,stayed=q.shift
  next if gone[[current,stayed]]
  gone[[current,stayed]]=true
  next_list=[]
  if stayed.size<4 && !stayed.include?(current)
    next_list<<[cost+s[current],current,(stayed+[current]).sort]
  end
  c[current].each{|k,v|
    next_list<<[cost+v,k,stayed]
  }
  next_list.each{|i|
    q.insert((0..q.size).bsearch{|j|q[j][0]>=i[0]},i) unless gone[[i[1],i[2]]]
  }
end
p q[0][0]