#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;
}