题解 | #牛群之间的体重比#

考察的知识点：哈希；

解答方法分析：

1. 创建一个空的无序图graph用于存储权重比例。
2. 遍历weightRatios和ratioValues列表，将每个比例对(a, b)及其值val添加到图中。同时，为了构建有向图，添加逆比例对(b, a)及其值1/val。
3. 创建一个空的结果列表res，用于存储查询的结果。
4. 对于每个查询(start, end)，执行以下操作：如果start或end不在图中，则将-1.0添加到res中，表示找不到路径。如果start和end相等，则将1.0添加到res中，表示两者比例相等。否则，执行广度优先搜索算法来寻找从start到end的路径：创建一个set集合visited用于存储已访问的节点。创建一个队列queue，并将起始节点start及其当前积curr_prod（初始为1）入队。创建一个布尔变量found，初始化为false。在队列不为空且找到路径之前循环执行以下步骤：出队队列中的节点node和当前积curr_prod。将节点node添加到visited中。遍历节点node的所有邻居neighbor及其对应的边权重edge_weight：如果邻居neighbor等于目标节点end，则说明找到了从start到end的路径，将curr_prod乘以edge_weight得到路径上的权重比例，将结果添加到res中，设置found为true，并跳出循环。如果邻居neighbor未访问过，则将邻居neighbor及curr_prod乘以edge_weight入队。如果没有找到路径（found仍为false），将-1.0添加到res中，表示找不到路径。
5. 返回结果列表res作为最终结果。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    vector<double> calcWeightRatios(vector<vector<string>>& weightRatios,
                                    vector<double>& ratioValues, vector<vector<string>>& questions) {
        unordered_map<string, unordered_map<string, double>> graph;
        for (int i = 0; i < weightRatios.size(); i++) {
            string a = weightRatios[i][0];
            string b = weightRatios[i][1];
            double val = ratioValues[i];
            graph[a][b] = val;
            graph[b][a] = 1.0 / val;
        }
        vector<double> res;
        for (auto& q : questions) {
            string start = q[0];
            string end = q[1];
            if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
                res.push_back(-1.0);
            } else if (start == end) {
                res.push_back(1.0);
            } else {
                unordered_set<string> visited;
                queue<pair<string, double>> q;
                bool found = false;
                q.push({start, 1});
                while (!q.empty() && !found) {
                    string node = q.front().first;
                    double curr_prod = q.front().second;
                    q.pop();
                    visited.insert(node);
                    for (auto& neighbor : graph[node]) {
                        string n = neighbor.first;
                        double weight = neighbor.second;
                        if (n == end) {
                            res.push_back(curr_prod * weight);
                            found = true;
                            break;
                        }
                        if (visited.find(n) == visited.end()) {
                            q.push({n, curr_prod * weight});
                        }
                    }
                }
                if (!found) {
                    res.push_back(-1.0);
                }
            }
        }
        return res;
    }
};