Submission #28975251

---

Source Code Expand

N,M,_,L = gets.split.map(&:to_i)
E1 = Array.new(N+1){[]}
E2 = Array.new(N+1){[]}
M.times{
	a,b,c = gets.split.map(&:to_i)
	e = c<2 ? E1 : E2
	e[a]<<b
	e[b]<<a
}

D,U = [L+1]*(N+1),{}
*Q = D[1] = x = 1
until Q.empty?
	while a = Q.shift
		d = x+U[a] = D[a]
		E1[a].each{|b|
			D[b] = d and Q<<b if d<D[b]
		}
	end
	while (a,d = U.shift)
		d += x
		E2[a].each{|b|
			D[b] = d and Q<<b if d<D[b]
		}
	end; U.clear
	x += x
end

puts$<.map{|t|
	L<D[t.to_i]?'Large':D[t.to_i]
}

Submission Info

Judge Result