Submission #30555571

---

Source Code Expand

class PQ
	def initialize
		@h = [] # min-heap
	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,M,K,L),A,B,*UVC = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N){[]}
UVC.each{|u,v,c|
	u -= 1; v -= 1
	E[u]<<[v,c]
	E[v]<<[u,c]
}

D = Array.new(N){[1.0/0,0,1.0/0]}
U = lambda{|d,u,a|
	d1,a1,d2 = D[u]
	next if d2<=d || a1==a&&d1<=d
	if a1==a
		D[u][0] = d
	elsif d<d1
		D[u] = d,a,d1
	else
		D[u][2] = d
	end
}
Q = PQ.new
B.each{|u|
	a = A[u-=1]
	U[0,u,a]
	Q.enq 0,[u,a]
}
while (d,(u,a) = Q.deq)
	d1,a1,d2 = D[u]
	E[u].each{|v,c|
		Q.enq d+c,[v,a] if U[d+c,v,a]
	} if d<=d1 || d<=d2&&a!=a1
end

puts A.map.with_index{|a,i|
	d1,a1,d2 = D[i]
	d = a!=a1 ? d1 : d2
	next d.finite? ? d : -1
}*' '

Submission Info

Judge Result