BUS 82/100 Biella 2022

Buongiorno a tutti, sto provando il problema bus della gara nazionale dell’anno scorso e funziona tutto ma ci sono 3 test case dove il mio programma va in execution time out. La mia soluzione prevede una sorta di bfs in cui a partire dal nodo 0 analizzo tutte le linee che passano per il primo nodo della queue del bfs e aggiorno un vettore D con i cambi minimi per arrivare ad ogni fermata presente su quelle linee. Se ottengo un valore D[n] migliore per un certo nodo n inserisco n nella queue. Alla fine restituisco il valore di D[N-1]. Potete aiutarmi a capire come posso migliorare il codice per non andare oltre il tempo massimo nei 3 test case che mi mancano? Grazie.
Vi allego il codice con la mia soluzione.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

vector<vector<pair<int,int>>> A;
vector <int> D;
int NN;
int LL;

void soluzione(int sorgente,vector<vector<int>> F){
	queue<int> Q;
	Q.push(sorgente);
	D[sorgente]=-1;
	while (Q.size()>0){
		int n_a=Q.front();
		Q.pop();
		for(int c=0;c<A[n_a].size();c++){
			pair<int,int> x=A[n_a][c];
			int linea=x.first;
			int pos=x.second;
			for (int i=pos+1;i<F[linea].size();i++){
				if(D[F[linea][i]]>D[n_a]+1){
					D[F[linea][i]]=D[n_a]+1;
					Q.push(F[linea][i]);
					if(F[linea][i]==NN-1){
						return;
					}
				}
			}
			A[n_a][c].second=F[linea].size();
		}
	}
	return;
}

int pianifica(int N, int L, vector<vector<int>> F){
	NN=N;
	LL=L;
	A.resize(N);
	for(int n=0;n<N;n++){
		D.push_back(INT_MAX);
	}
	for(int l=0;l<F.size();l++){
		vector<pair<int,int>> X;
		for(int p=0;p<F[l].size();p++){
			pair<int,int> x;
			x.first=l;
			x.second=p;
			A[F[l][p]].push_back(x);
		}
	}
	soluzione(0,F);
	if (D[N-1]==INT_MAX){
		return -1;
	}
	return D[N-1];
}

Per prendere il punteggio pieno devi valutare anche i casi in cui non si ha un valore D[n] migliore quando si visita il nodo n.