【每日算法Day 62】LeetCode 815公交路线

classSolution {
public: 
intnumBusesToDestination(vector<vector<int>>&routes, intS, 
intT) {  
if (S==T) return0; 
intn=routes.size();  
for (inti=0; i<n; ++i) {  
sort(routes[i].begin(), routes[i].end()); 
routes[i].erase(unique(routes[i].begin(), 
routes[i].end()), 
routes[i].end());  
        }     
routes.push_back({S});  
routes.push_back({T});  
vector<vector<int>>G=buildGraph(routes, S, T);   
returnBFS(G);    }
vector<vector<int>>buildGraph(vector<vector<int>>&routes, intS, intT) {   
intn=routes.size();  
vector<vector<int>>G(n);  
for (inti=0; i<n; ++i) {  
for (intj=i+1; j<n; ++j) {   
intsu=routes[i].size(), sv=routes[j].size(); 
intu=0, v=0;    
while (u<su&&v<sv) {  
if (routes[i][u] <routes[j][v]) ++u;  
elseif (routes[i][u] >routes[j][v]) ++v;   
else {            
G[i].push_back(j);   
G[j].push_back(i);   
break;    
                    }           
                }         
            }     
        }    
returnG; 
    }
intBFS(vector<vector<int>>&G) {    
intn=G.size();    
intS=n-2;    
intT=n-1;   
vector<int>dis(n, -1); 
queue<int>Q;   
Q.push(S);     
dis[S] =0;   
while (!Q.empty()) {  
intu=Q.front();   
Q.pop();      
for (inti=0, sz=G[u].size(); i<sz; ++i) {  
intv=G[u][i];   
if (dis[v] ==-1) {      
Q.push(v); 
dis[v] =dis[u] +1;    
if (v==T) returndis[v]-1; 
                }      
            }    
        } 
return-1; 
    }
};