Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- bool czy_jest(vector<int> tablica, int miasto)
- {
- for(unsigned i = 0; i < tablica.size(); ++i)
- if(tablica[i] == miasto)
- return true;
- return false;
- }
- class Drogi
- {
- int** drogi;
- int suma;
- int ile_miast;
- public:
- Drogi(int n);
- ~Drogi();
- void dodajDroge(int a, int b, int d);
- void usunDroge(int a, int b);
- int sumaDlugosci();
- void drogiZMiasta(int a);
- bool jestTrasa(int a, int b);
- };
- Drogi::Drogi(int n) : ile_miast(n), drogi(nullptr), suma(0)
- {
- drogi = new int*[n];
- for(int i = 0; i < n; ++i)
- drogi[i] = new int[n];
- for(int i = 0; i < n; ++i)
- for(int j = 0; j < n; ++j)
- drogi[i][j] = 0;
- }
- Drogi::~Drogi()
- {
- for(int i = 0; i < ile_miast; ++i)
- delete[] drogi[i];
- delete[] drogi;
- }
- void Drogi::dodajDroge(int a, int b, int d)
- {
- drogi[a][b] = d;
- drogi[b][a] = d;
- suma += d;
- }
- int Drogi::sumaDlugosci()
- {
- return suma;
- }
- void Drogi::usunDroge(int a, int b)
- {
- suma -= drogi[a][b];
- drogi[a][b] = 0;
- drogi[b][a] = 0;
- }
- void Drogi::drogiZMiasta(int a)
- {
- cout << "Drogi z miasta nr " << a << ":\n";
- for(int i = 0; i < ile_miast; ++i)
- if(drogi[a][i] > 0)
- cout << "Droga do miasta nr " << i << " o dlugosci " << drogi[a][i] << endl;
- }
- bool Drogi::jestTrasa(int a, int b)
- {
- if(drogi[a][b] > 0)
- return true;
- vector<int> miasta;
- miasta.clear();
- for(int i = 0; i < ile_miast; ++i)
- if(drogi[a][i] > 0)
- miasta.push_back(i);
- bool flaga;
- do
- {
- flaga = false;
- for(unsigned i = 0; i < miasta.size(); ++i)
- {
- for(int j = 0; j < ile_miast; ++j)
- if(drogi[i][j] > 0)
- if(!czy_jest(miasta, j))
- {
- if(j == b)
- return true;
- flaga = true;
- miasta.push_back(j);
- }
- }
- }
- while(flaga);
- return false;
- }
- int main()
- {
- Drogi siec(10);
- siec.dodajDroge(1, 3, 7);
- siec.dodajDroge(3, 5, 10);
- siec.dodajDroge(1, 8, 9);
- siec.drogiZMiasta(1);
- cout << siec.jestTrasa(3, 8) << endl; // 1
- cout << siec.sumaDlugosci() << endl; // 26
- siec.usunDroge(1, 8);
- cout << siec.jestTrasa(3, 8) << endl; // 0
- cout << siec.sumaDlugosci() << endl; // 17
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement