#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int miasto[401],miastoX[401],miastoY[401],wybrane[401];
int odwiedzone[401];
int tab[401];
int iloscM,maxx,najtrasa;
int najlepszy;
int droga( int suma,long int profit,int poprz,int ilosc)
{
int i,j;
int odleglosc,powrot;
for(i=2;i<=iloscM;i++)
{
odleglosc=rintf(sqrt((miastoX[i]-miastoX[poprz])*(miastoX[i]-miastoX[poprz])+(miastoY[i]-miastoY[poprz])*(miastoY[i]-miastoY[poprz])));
powrot=rintf(sqrt(((miastoX[1]-miastoX[i])*(miastoX[1]-miastoX[i])+(miastoY[1]-miastoY[i])*(miastoY[1]-miastoY[i]))));
if(odleglosc+suma+powrot<=maxx && odwiedzone[i]==0 && miasto[i]!=0){
suma=suma+odleglosc;
profit=profit+miasto[i];
odwiedzone[i]=1;
ilosc++;
tab[ilosc]=i;
if(najlepszy<=profit){
if(najlepszy==profit&&suma+powrot<najtrasa)
{
for(j=1;j<=iloscM;j++){
wybrane[j]=tab[j];
}
najlepszy=profit;
najtrasa=suma+powrot;
}
if(najlepszy!=profit){
for(j=1;j<=iloscM;j++){
wybrane[j]=tab[j];
}
najlepszy=profit;
najtrasa=suma+powrot;
}
}
droga(suma,profit,i,ilosc);
tab[ilosc]=0;
ilosc--;
odwiedzone[i]=0;
suma=suma-odleglosc;
profit=profit-miasto[i];
}
}
}
int main()
{
FILE *fp;
int i;
ifstream plikin;
plikin.open("in1.txt");
plikin>>iloscM>>maxx;
for(i=1;i<=iloscM;i++)
{
plikin>>miastoX[i]>>miastoY[i]>>miasto[i];
tab[i]=0;
odwiedzone[i]=0;
wybrane[i]=0;
}
int odwiedzone[iloscM],tab[iloscM];
wybrane[0]=1;
odwiedzone[1]=1;
droga(0,0,1,1);
printf("Najlepszy profit: %d\n",najlepszy);
for(i=0;i<=iloscM;i++)
{
if(wybrane[i]!=0)
{
printf("%d ",wybrane[i]);
}
}
printf(" 1 \nDlugosc trasy: %d", najtrasa);
// system("PAUSE");
return 0;
}
{"html5":"htmlmixed","css":"css","javascript":"javascript","php":"php","python":"python","ruby":"ruby","lua":"text\/x-lua","bash":"text\/x-sh","go":"go","c":"text\/x-csrc","cpp":"text\/x-c++src","diff":"diff","latex":"stex","sql":"sql","xml":"xml","apl":"apl","asterisk":"asterisk","c_loadrunner":"text\/x-csrc","c_mac":"text\/x-csrc","coffeescript":"text\/x-coffeescript","csharp":"text\/x-csharp","d":"d","ecmascript":"javascript","erlang":"erlang","groovy":"text\/x-groovy","haskell":"text\/x-haskell","haxe":"text\/x-haxe","html4strict":"htmlmixed","java":"text\/x-java","java5":"text\/x-java","jquery":"javascript","mirc":"mirc","mysql":"sql","ocaml":"text\/x-ocaml","pascal":"text\/x-pascal","perl":"perl","perl6":"perl","plsql":"sql","properties":"text\/x-properties","q":"text\/x-q","scala":"scala","scheme":"text\/x-scheme","tcl":"text\/x-tcl","vb":"text\/x-vb","verilog":"text\/x-verilog","yaml":"text\/x-yaml","z80":"text\/x-z80"}