3 ms C++ BFS two queues


  • 0
    I
    class Solution {
    public:
        double solve(string a, string b, unordered_map<string,unordered_map<string,double>> &m)
        {
            if(a == b)
            {
                if(m.find(a) != m.end())
                   return 1.0;
                return -1.0;
            }
            queue<string> q;
            queue<double> qf;
            q.push(a);
            qf.push(1.0);
            unordered_set<string> visited;
            visited.insert(a);
            while(!q.empty())
            {
                    for(auto it = m[q.front()].begin(); it != m[q.front()].end(); ++it)
                    {
                       if(visited.find(it->first) != visited.end())
                          continue;
                       if(it->first == b)
                          return qf.front()*it->second;
                       q.push(it->first);
                       qf.push(it->second*qf.front());
                       visited.insert(it->first);
                    }
                    q.pop();
                    qf.pop();
            }
            return -1;
        }
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
             unordered_map<string,unordered_map<string,double>> m;
             for(int i = 0; i < equations.size(); ++i)
             {
                 m[equations[i].first][equations[i].second] = values[i];
                 m[equations[i].second][equations[i].first] = 1.0/values[i];
             }
             vector<double> res;
             for(int i = 0; i < query.size(); ++i)
             {
                 res.push_back(solve(query[i].first,query[i].second,m));
             }
             return res;
        }
    };
    

Log in to reply
 

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