1709. Penguin-Avia - Timus

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    /* Trebuie sa obtinem in final un graf conex cu numar minim de muchii si sa avem un cost cat
    mai mic al operatiilor din enunt, deci o sa legam toate componentele de componenta unui nod
    (l-am ales pe 0). De asemenea, fiecare componenta o transformam in arborele sau partial de cost
    minim pentru a obtine numar de muchii minim la final.
    */
    int N, D, A;
    cin >> N >> D >> A;
    vector < string > a(N); // matricea initiala pe care o vom si transforma intr-una rezultat
    for(int i = 0; i < N; ++i)
        cin >> a[i];
    vector < bool > viz(N); // daca am ajuns la nodul i sau nu
    long long ans = 0; // rezultatul
    for(int i = 0; i < N; ++i) // Facem Componente Conexe + MST pe fiecare componenta
        if(!viz[i]) { // daca i nu e vizitat vedem de el
            if(i != 0) {
                a[0][i] = a[i][0] = 'a'; // daca nu e 0 nod il legam de acesta
                ans += A; // adaugam costul operatiei de legare la rezultat
            }
            queue < int > Q; // pornim cu BFS
            Q.emplace(i); // adaugam i in coada
            viz[i] = true; // marcam i vizitat
            while(!Q.empty()) {
                int node = Q.front();
                Q.pop();
                for(int vec = 0; vec < N; ++vec)
                    if(a[node][vec] == '1') { // daca muchia i -> vec exista
                        if(!viz[vec]) { // daca vecinul nu e vizitat se va afla la final inca in compoenta conexa a lui i
                            a[node][vec] = a[vec][node] = '0';
                            viz[vec] = true; // marcam vec ca vizitat
                            Q.emplace(vec); // adaugam vec in coada, pentru a parcurge in continuare componenta actuala
                        }
                        else { // daca vecinul e deja vizitat nu mai avem nevoie de aceasta muchie
                            a[node][vec] = a[vec][node] = 'd'; // ii dam cancel
                            ans += D; // crestem rezultatul cu costul operatiei de cancel
                        }
                    }
            }
            cout << ans << '\n'; // afisam rezultatele
            for(int i = 0; i < N; ++i , cout << '\n')
                for(int j = 0; j < N; ++j)
                    cout << a[i][j];
        }
    cout << ans << '\n'; // afisam rezultatele
    for(int i = 0; i < N; ++i , cout << '\n')
        for(int j = 0; j < N; ++j)
            cout << a[i][j];
}