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

• 题目考察的知识点 : 哈希，BFS
• 题目解答方法的文字分析：

1. 使用字典 graph 存储图中的边和权重。对于每个等式 (a, b)，在 graph[a] 中添加边 (b, val)，在 graph[b] 中添加边 (a, 1/val)。
2. 遍历查询列表 questions，对于每个查询 (start, end) 进行如下操作：如果 start 或 end 不在 graph 中，则无法计算答案，将其设为 -1.0 并加入结果列表 res。如果 start 和 end 相同，则 a/a=1.0，将其设为 1.0 并加入结果列表 res。否则，使用广度优先搜索遍历从 start 出发能够到达的所有节点，并计算从 start 到当前节点所经过的边的权重之积，直到找到 end 或者遍历完图为止。如果找到了 end，则将从 start 到 end 所经过的边的权重之积加入结果列表 res，否则将其设为 -1.0 并加入结果列表 res。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param weightRatios string字符串二维数组
# @param ratioValues double浮点型一维数组
# @param questions string字符串二维数组
# @return double浮点型一维数组
#
from collections import defaultdict


class Solution:
    def calcWeightRatios(
        self,
        weightRatios: List[List[str]],
        ratioValues: List[float],
        questions: List[List[str]],
    ) -> List[float]:
        graph = defaultdict(dict)

        # 构建图
        for (a, b), val in zip(weightRatios, ratioValues):
            graph[a][b] = val
            graph[b][a] = 1.0 / val

        # 处理查询
        res = []
        for start, end in questions:
            if start not in graph or end not in graph:
                res.append(-1.0)
            elif start == end:
                res.append(1.0)
            else:
                visited = set()
                queue = [(start, 1)]
                found = False
                while queue and not found:
                    node, curr_prod = queue.pop(0)
                    visited.add(node)
                    for neighbor, edge_weight in graph[node].items():
                        if neighbor == end:
                            res.append(curr_prod * edge_weight)
                            found = True
                            break
                        if neighbor not in visited:
                            queue.append((neighbor, curr_prod * edge_weight))
                if not found:
                    res.append(-1.0)

        return res