Submission #26823765

---

Source Code Expand

(N,X),*ABC = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N){[]}
ABC.each{|a,b,c|
	a -= 1; b -= 1
	E[a]<<[b,c]
	E[b]<<[a,c]
}
D = lambda{|ds,o,s|
	x,ds[s],*q = X-o,-o,s
	while a = q.pop
		next if x <= d = ds[a]
		E[a].each{|b,c|
			next if ds[b] <= c += d
			ds[b] = c
			q << b
		}
	end
	next ds,o
}

Ds = [nil]*N
Ds[0] = [[10**9]*N,0,0]
*Q = 0
while a = Q.pop
	ds,o = Ds[a] = D[*Ds[a]]
	E[a].each{|b,|
		next if Ds[b]
		Ds[b] = [ds.dup,ds[b]-ds[a]+o,b]
		Q << b
	}
end

puts(Ds.any?{|ds,o| ds.any? X-o }?'Yes':'No')

Submission Info

Judge Result