simple Cpp BFS 0ms


  • 0
    U
    class Solution {
    public:
        double gSearch(map<string,vector<pair<double,string>>> &M, string start, string end) {
            set<string>visited;
            queue<pair<string,double>>Q;
            Q.push({start,1.0});
            visited.insert(start);
            while(!Q.empty())
            {
                auto f = Q.front();
                Q.pop();
                auto a = M[f.first];
                for(auto b:a)
                {
                    if(b.second == end)
                    {
                        return f.second*b.first;
                    }
                    else if (visited.find(b.second) == visited.end())
                    {
                        visited.insert(b.second);
                        Q.push({b.second, f.second*b.first});
                    }
                }
            }
            return -1.0;
        }
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            map<string,vector<pair<double,string>>>adj;
            for(unsigned u=0; u<equations.size(); u++) {
                auto a = equations[u];
               if(adj.find(a.first) != adj.end()) {
                   adj[a.first].push_back({values[u], a.second});
               } 
               else {
                   adj[a.first] = vector<pair<double,string>>(1,{values[u], a.second});
               }
               
               if(adj.find(a.second) != adj.end()) {
                   adj[a.second].push_back({1.0/values[u], a.first});
               } 
               else {
                   adj[a.second] = vector<pair<double,string>>(1,{1.0/values[u], a.first});
               }
            }
            
            vector<double>ret;
            for(auto a:queries)
            {
                ret.push_back(gSearch(adj, a.first, a.second));
            }
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.