ultimoDaLista([A],A).
ultimoDaLista([_|L], R):- ultimoDaLista(L,R).

listIsEmpty([]):-true.
listIsEmpty([_|_]):-false.

% pesquisa termina quando a lista de novos elementos estiver vazia (só resta a cidade vizinha)
bnb(A,Cam,Custo):-
	%findall(city(B,_,_), (B\==A), New),
	city(A,_,_),
	bnb2(A,[(0,[A])],Cam,Custo).


bnb2(A,[(Custo,[A|T])|T2],Cam,Custo):-
	Custo > 0,
	L = [A|T],
	reverse(L,Cam).

bnb2(A,[(Ca,LA)|Outros],Cam,Custo):-
	%procura todas as cidades q conectam ao destino atual
	LA = [X|_],
	findall((CaX,[NovaCidade|LA]),(city(NovaCidade,_,_),\+member(NovaCidade, LA),dist_cities(NovaCidade,X, Ca2), CaX is Ca + Ca2),Novos),
	ultimoDaLista(LA,U),
	(listIsEmpty(Novos),dist_cities(X,U, Dist),Cax2 is Ca+Dist, Novos2 = [(Cax2,[U|LA])], append(Outros,Novos2,Todos);\+listIsEmpty(Novos),append(Outros,Novos,Todos)),
	sort(Todos,TodosOrd),
	bnb2(A,TodosOrd,Cam,Custo).