%1

tsp1(Orig,L,C):-setof((Custo,Laux),(aux(Orig,Laux,Custo)),R),res(R,L,C).
res([(C,L)|_],L,C).

aux(Orig,Cam,Custo):-todas(L),length(L,N1),vai(Orig,Orig,N1,[Orig],Cam,0,Custo).
todas(L):-findall(X,(city(X,_,_)),L).
vai(Orig,Atual,Ncidades,LA,[Orig|LA],Caux,Custo):-Ncidades ==1,dist_cities(Orig,Atual,Dist),Custo is Dist+Caux,!.
vai(Orig,Atual,Ncidades,LA,Cam,Caux,Custo):-city(X,_,_),\+member(X,LA),Naux is Ncidades -1,
dist_cities(Atual,X,Dist),CustoAux is Caux+Dist,vai(Orig,X,Naux,[X|LA],Cam,CustoAux,Custo).