Evaluate Division（C++除法求值）-蒲公英云

Evaluate Division（C++除法求值）

清疚 2022-09-08 03:40 87阅读 0赞

(1) bfs

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& e, vector<double>& v, vector<vector<string>>& q) {
        unordered_map<string,int> mp;
        int number=0;
        for(int i=0;i<e.size();i++) {
            if(mp.find(e[i][0])==mp.end()) {
                mp[e[i][0]]=number;
                number++;
            }
            if(mp.find(e[i][1])==mp.end()) {
                mp[e[i][1]]=number;
                number++;
            }
        }
        vector<vector<pair<int,double>>> edge(number);
        for(int i=0;i<e.size();i++) {
            edge[mp[e[i][0]]].push_back({mp[e[i][1]],v[i]});
            edge[mp[e[i][1]]].push_back({mp[e[i][0]],1/v[i]});
        }
        vector<double> result;
        for(int i=0;i<q.size();i++) {
            double temp=-1.0;
            if(mp.find(q[i][0])!=mp.end() && mp.find(q[i][1])!=mp.end()) {
                int a=mp[q[i][0]];
                int b=mp[q[i][1]];
                if(a==b) {
                    temp=1.0;
                    result.push_back(temp);
                    continue;
                }
                queue<int> qe;
                vector<double> d(number,-1.0);
                d[a]=1.0;
                qe.push(a);
                while(!qe.empty() && d[b]<0) {
                    int t=qe.front();
                    qe.pop();
                    for(int i=0;i<edge[t].size();i++) {
                        if(d[edge[t][i].first]<0) {
                            d[edge[t][i].first]=edge[t][i].second*d[t];
                            qe.push(edge[t][i].first);
                        }
                    }
                }
                temp=d[b];
            }
            result.push_back(temp);
        }
        return result;
    }
};