Advertisement
MeehoweCK

Untitled

Jun 18th, 2019
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. bool czy_jest(vector<int> tablica, int miasto)
  7. {
  8.     for(unsigned i = 0; i < tablica.size(); ++i)
  9.         if(tablica[i] == miasto)
  10.             return true;
  11.     return false;
  12. }
  13.  
  14. class Drogi
  15. {
  16.     int** drogi;
  17.     int suma;
  18.     int ile_miast;
  19. public:
  20.     Drogi(int n);
  21.     ~Drogi();
  22.     void dodajDroge(int a, int b, int d);
  23.     void usunDroge(int a, int b);
  24.     int sumaDlugosci();
  25.     void drogiZMiasta(int a);
  26.     bool jestTrasa(int a, int b);
  27. };
  28.  
  29. Drogi::Drogi(int n) : ile_miast(n), drogi(nullptr), suma(0)
  30. {
  31.     drogi = new int*[n];
  32.     for(int i = 0; i < n; ++i)
  33.         drogi[i] = new int[n];
  34.     for(int i = 0; i < n; ++i)
  35.         for(int j = 0; j < n; ++j)
  36.             drogi[i][j] = 0;
  37. }
  38.  
  39. Drogi::~Drogi()
  40. {
  41.     for(int i = 0; i < ile_miast; ++i)
  42.         delete[] drogi[i];
  43.     delete[] drogi;
  44. }
  45.  
  46. void Drogi::dodajDroge(int a, int b, int d)
  47. {
  48.     drogi[a][b] = d;
  49.     drogi[b][a] = d;
  50.     suma += d;
  51. }
  52.  
  53. int Drogi::sumaDlugosci()
  54. {
  55.     return suma;
  56. }
  57.  
  58. void Drogi::usunDroge(int a, int b)
  59. {
  60.     suma -= drogi[a][b];
  61.     drogi[a][b] = 0;
  62.     drogi[b][a] = 0;
  63. }
  64.  
  65. void Drogi::drogiZMiasta(int a)
  66. {
  67.     cout << "Drogi z miasta nr " << a << ":\n";
  68.     for(int i = 0; i < ile_miast; ++i)
  69.         if(drogi[a][i] > 0)
  70.             cout << "Droga do miasta nr " << i << " o dlugosci " << drogi[a][i] << endl;
  71. }
  72.  
  73. bool Drogi::jestTrasa(int a, int b)
  74. {
  75.     if(drogi[a][b] > 0)
  76.         return true;
  77.     vector<int> miasta;
  78.     miasta.clear();
  79.     for(int i = 0; i < ile_miast; ++i)
  80.         if(drogi[a][i] > 0)
  81.             miasta.push_back(i);
  82.     bool flaga;
  83.  
  84.     do
  85.     {
  86.         flaga = false;
  87.         for(unsigned i = 0; i < miasta.size(); ++i)
  88.         {
  89.             for(int j = 0; j < ile_miast; ++j)
  90.                 if(drogi[i][j] > 0)
  91.                     if(!czy_jest(miasta, j))
  92.                     {
  93.                         if(j == b)
  94.                             return true;
  95.                         flaga = true;
  96.                         miasta.push_back(j);
  97.                     }
  98.         }
  99.     }
  100.     while(flaga);
  101.  
  102.     return false;
  103. }
  104.  
  105. int main()
  106. {
  107.     Drogi siec(10);
  108.     siec.dodajDroge(1, 3, 7);
  109.     siec.dodajDroge(3, 5, 10);
  110.     siec.dodajDroge(1, 8, 9);
  111.     siec.drogiZMiasta(1);
  112.     cout << siec.jestTrasa(3, 8) << endl;       // 1
  113.     cout << siec.sumaDlugosci() << endl;        // 26
  114.     siec.usunDroge(1, 8);
  115.     cout << siec.jestTrasa(3, 8) << endl;       // 0
  116.     cout << siec.sumaDlugosci() << endl;        // 17
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement