Submission #14141040

---

Source Code Expand

class PQ
	K,V = *0..1

	def initialize
		@h = [] # min-heap
	end

	def enq k,v
		@h.push [k,v]
		up_heap
	end

	def deq
		max, last = @h[0], @h.pop
		unless @h.empty?
			@h[0] = last
			dn_heap
		end
		return *max
	end

private
	def up_heap
		i, up = @h.size-1, @h[-1]
		while 0 <= (iP = (i-1)/2)
			break unless up[K] < @h[iP][K]
			@h[i], i = @h[iP], iP
		end
		@h[i] = up
	end

	def dn_heap
		i, dn, sz = 0, @h[0], @h.size
		while (iC = 2*i+1) < sz
			iC += 1 if iC+1 < sz and @h[iC+1][K] < @h[iC][K]
			break unless @h[iC][K] < dn[K]
			@h[i], i = @h[iC], iC
		end
		@h[i] = dn
	end
end

N,M = gets.split.map(&:to_i)
E = Array.new(N+1){ [] }
M.times{
	u,v = gets.split.map(&:to_i)
	E[u]<<v
	E[v]<<u
}
S = gets.to_i
K = gets.to_i
T = gets.split.map(&:to_i)

C = lambda{|s,t|
	cost,q,visited = 0,[s],{s=>true}
	until q.include? t
		q = q.map{|u|E[u]}.inject(:|).select{|_| ! visited[_] && (visited[_]=true) }
		cost+=1
	end
	next cost
}
E2 = Hash.new{|h,u|h[u]=[]}
V = [S,*T]
V.combination(2){|s,t|
	c = C[s,t]
	E2[s]<<[t,c]
	E2[t]<<[s,c]
}
Visit = Hash[*V.map.with_index{|v,i| [v,1<<i] }.flatten]
Visited = lambda{
	h = {}
	return lambda{|u,visited|
		k = u<<K+1 | visited | Visit[u]
		return h[k] || ! (h[k]=true)
	}
}.call
Q = PQ.new
Q.enq 0,[S,1]
while (c,(u,visited) = Q.deq)
	if visited == (1<<K+1)-1
		p c
		break
	end
	E2[u].each{|v,cv|
		next if Visited[v,visited]
		Q.enq c+cv,[v,visited|Visit[v]]
	}
end

Submission Info

Judge Result