Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 399. Evaluate Division

---

參考資訊：
https://blog.csdn.net/fuxuemingzhu/article/details/82591165
https://samiulmushfik.medium.com/leetcode-399-evaluate-division-6bcd7ffff05c

題目：


方法(向量圖概念)：


解答：

class Solution {
public:
    vector<double> calcEquation(
        vector<vector<string>>& equations,
        vector<double>& values,
        vector<vector<string>>& queries)
    {
        vector<double> r;
        unordered_map<string, unordered_map<string, double>> cost;

        for (int i = 0; i < equations.size(); i++) {
            double c = values[i];
            string s0 = equations[i][0];
            string s1 = equations[i][1];

            cost[s0][s1] = c;
            cost[s1][s0] = 1.0 / c;
        }

        for (auto& q : queries) {
            unordered_set<string> visited;

            double t = dfs(q[0], q[1], cost, visited);
            r.push_back((t > 0.0) ? t : -1.0);
        }

        return r;
    }

    double dfs(
        string e0,
        string e1,
        unordered_map<string, unordered_map<string, double>>& cost,
        unordered_set<string>&visited)
    {
        if (cost[e0].count(e1)) {
            return cost[e0][e1];
        }

        for (auto& n : cost[e0]) {
            if (visited.count(n.first) == 0) {
                visited.insert(n.first);
                double r = dfs(n.first, e1, cost, visited);
                if (r > 0.0) {
                    return r * n.second;
                }
            }
        }

        return -1.0;
    }
};