825. Bus Station

Code(Language:C++) (Judger:cloudjudge-cluster-9)

class Solution {
public:
    /**
     * @param N: The number of buses
     * @param route: The route of buses
     * @param A: Start bus station
     * @param B: End bus station
     * @return: Return the minimum transfer number
     */
    int getMinTransferNumber(int N, vector<vector<int>> &route, int A, int B) {
        // Write your code here
        // BFS
        // 当有一些思路，不知道怎么进行时，就考虑建立变量之间的mapping关系
        const int size = route.size(); 
        unordered_map<int, vector<int>> station2Bus; 
        for(int i = 0; i < size; i++){
            for(int j = 0; j < route[i].size(); j++){
                station2Bus[route[i][j]].push_back(i); 
            }
        }
        std::queue<int> q;
        q.push(A); 
        int res = 1; 
        unordered_set<int> visited; 
        visited.insert(A); 
        while(!q.empty()){
            int sizeQ = q.size();
            for(int i = 0; i < sizeQ; i++){
                int station = q.front();
                q.pop(); 
                for(auto bus : station2Bus[station]){
                    for(int j = 0; j < route[bus].size(); j++){
                        if(route[bus][j] == B){
                            return res; 
                        }
                        if(visited.count(route[bus][j])){
                            continue; 
                        }
                        visited.insert(route[bus][j]);
                        q.push(route[bus][j]); 
                    }
                }
            }
            res++; 
        }
        return -1; 
    }
};