1. #include <iostream>
2. #include <fstream>
3. #include <cmath>
4.      
5. using namespace std;
6.      
7. int miasto[401],miastoX[401],miastoY[401],wybrane[401];
8. int odwiedzone[401];
9. int tab[401];
10. int iloscM,maxx,najtrasa;
11. int najlepszy;
12.      
13. int droga( int suma,long int profit,int poprz,int ilosc)
14. {
15.     int i,j;
16.     int odleglosc,powrot;
17.        
18.        
19.     for(i=2;i<=iloscM;i++)
20.     {    
21.         odleglosc=rintf(sqrt((miastoX[i]-miastoX[poprz])*(miastoX[i]-miastoX[poprz])+(miastoY[i]-miastoY[poprz])*(miastoY[i]-miastoY[poprz])));
22.         powrot=rintf(sqrt(((miastoX[1]-miastoX[i])*(miastoX[1]-miastoX[i])+(miastoY[1]-miastoY[i])*(miastoY[1]-miastoY[i]))));
23.                      
24.         if(odleglosc+suma+powrot<=maxx && odwiedzone[i]==0 && miasto[i]!=0){
25.             suma=suma+odleglosc;
26.             profit=profit+miasto[i];      
27.             odwiedzone[i]=1;
28.             ilosc++;
29.             tab[ilosc]=i;
30.            
31.                         if(najlepszy<=profit){
32.                
33.                                 if(najlepszy==profit&&suma+powrot<najtrasa)
34.                 {                
35.                         for(j=1;j<=iloscM;j++){
36.                             wybrane[j]=tab[j];
37.                         }
38.                         najlepszy=profit;
39.                         najtrasa=suma+powrot;
40.                 }
41.                    
42.                         if(najlepszy!=profit){  
43.                         for(j=1;j<=iloscM;j++){
44.                                 wybrane[j]=tab[j];
45.                             }
46.                             najlepszy=profit;
47.                             najtrasa=suma+powrot;
48.                     }
49.             }
50.                
51.             droga(suma,profit,i,ilosc);
52.             tab[ilosc]=0;
53.             ilosc--;            
54.             odwiedzone[i]=0;    
55.             suma=suma-odleglosc;
56.             profit=profit-miasto[i];
57.      
58.         }
59.     }
60. }
61.      
62. int main()
63. {
64.     FILE *fp;
65.     int i;
66.        
67.     ifstream plikin;
68.     plikin.open("in1.txt");
69.     plikin>>iloscM>>maxx;
70.            
71.     for(i=1;i<=iloscM;i++)
72.     {
73.         plikin>>miastoX[i]>>miastoY[i]>>miasto[i];
74.                 tab[i]=0;
75.         odwiedzone[i]=0;
76.         wybrane[i]=0;
77.     }
78.        
79.     int odwiedzone[iloscM],tab[iloscM];
80.    
81.     wybrane[0]=1;
82.     odwiedzone[1]=1;
83.      
84.     droga(0,0,1,1);
85.     printf("Najlepszy profit: %d\n",najlepszy);
86.     for(i=0;i<=iloscM;i++)
87.     {
88.         if(wybrane[i]!=0)
89.         {
90.                 printf("%d ",wybrane[i]);
91.         }
92.     }
93.     printf(" 1 \nDlugosc trasy: %d", najtrasa);
94.        // system("PAUSE");
95.         return 0;
96. }
97.