Cacci agli interruttori - troppo tempo

Aiuto
1

Sono alle prime armi con l’algoritmo bfs, e sto avendo problemi con il problema terry “caccia agli interruttori”. All’inizio avevo creato questo post perché pensavo di aver sbagliato qualcosa nel codice. Ho scoperto che invece ci metteva semplicemente TROPPO tempo, (per fare il 15esimo input ci metteva circa 15 minuti…). Gli output che ottiene sono comunque giusti, ma lascerò comunque questo post perché mi chiedevo come si potesse ottimizzare la cosa (15 minuti per un input non sono proprio il massimo…). Mi scuso in anticipo se si tratta di un errore stupido, sono ancora alle prime armi su questo tipi di algoritmi. Questo è il mio codice, per ogni interruttore cerca la strada più veloce usando bfs per arrivare ad un interruttore di tipo 1. Appena arriva a un interruttore di tipo 1 ritorna la strada più veloce per arrivare a quell’interruttore. Confronta l’output ottenuto con gli altri interruttori e restituisce quello maggiore:

#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int bfs(int start, const vector<vector<int>>& adVect, const vector<int>& findThis){

    if (count(findThis.begin(), findThis.end(), start) > 0){
        return 1;
    }
    vector<bool> visitati(adVect.size(), false);
    queue<int> q;
    visitati[start] = true;
    q.push(start);

    bool foundIt = false;
    int road = 1;
    while(!foundIt){
        int qsize = q.size();
        road++;
        if (q.empty()){
            return -1;
        }
        for (int i = 0; i<qsize; i++){
            int node = q.front();
            q.pop();
            for (int ad : adVect[node]){
                if (!visitati[ad]){
                    visitati[ad] = true;
                    q.push(ad);
                    if (count(findThis.begin(), findThis.end(), ad) > 0){
                        foundIt = true;
                    }
                }
            }
        }
    }
    return road;
}

void solve(int t) {
    int N, A, B;
    cin >> N >> A >> B;

    vector<int> Z(A), X(B), Y(B);
    
    for (int i = 0; i < A; i++) {
        cin >> Z[i];
    }

    for (int i = 0; i < B; i++) {
        cin >> X[i] >> Y[i];
    }

    vector<vector<int>> adVect(N);

    for (int i = 0; i < B; i++){
        adVect[X[i]].push_back(Y[i]);
        adVect[Y[i]].push_back(X[i]);
    }

    int num = 0;
    int idx = 0;
    int compare = 0;
    for (int i = 0; i<N; i++){
        compare = bfs(i, adVect, Z);
        if (num < compare){
            num = compare;
            idx = i;
        }
    }

    cout << "Case #" << t << ": " << idx << " " << num << "\n";
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}