Facebook
From Botched Bird, 10 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 561
  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.