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]