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