Submission #32487597

---

Source Code Expand

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

	def top_c
		return @h[0][0] if @h[0]
	end
 
	def enq c,a
		@h << [c,a]
		up_heap
	end
	def deq
		return unless @h[0]
		@h[0],@h[-1] = @h[-1],@h[0]
		c,a = @h.pop
		dn_heap if @h[0]
		return c,a
	end
 
private
	def up_heap
		c, = up = @h[i=@h.size-1]
		while 0<i
			iP = (i-1)/2
			break if @h[iP][0]<=c
			@h[i],i = @h[iP],iP
		end
		@h[i] = up
	end
	def dn_heap
		c, = dn = @h[i=0]
		z = @h.size
		until z <= iC = i+i+1
			iC += 1 if iC+1<z && @h[iC+1][0]<@h[iC][0]
			break if c<=@h[iC][0]
			@h[i],i = @h[iC],iC
		end
		@h[i] = dn
	end
end

(N,),*ABC,X = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N+1){[]}
ABC.each{|a,b,c|
	E[a]<<[b,c]
	E[b]<<[a,c]
}

V = [nil]*(N+1)
V[1] = v = 1
W = PQ.new
E[1].each{|b,c| W.enq c,b }
puts X.map{|x,*as|
	while W.top_c&.<= x
		_,a = W.deq
		next if V[a]
		V[a] = v += 1
		as<<a
	end
	while a = as.pop
		E[a].each{|b,c|
			W.enq c,b if ! V[b]
		}
	end
	next v
}

Submission Info

Judge Result