【leetcode】399. 除法求值（evaluate-division）（模拟）[中等]

链接

https://leetcode-cn.com/problems/evaluate-division/

耗时

解题：1 h 37 min
题解：26 min

题意

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

思路

以变量作为节点，变量相除的值作为边权建图，那么问题 Cj / Dj 是否有确定的答案即等价于在建的图上变量 Cj 的节点能否到达变量 Dj 的节点，如果能到达，Cj / Dj 的答案即是 Cj 到 Dj 这条路上所有边权的乘积，不能到达则无法确定答案返回-1.0。

AC代码

class Solution {
public:
    struct node {
        int to;
        double cost;
    };
    vector<node> E[50];
    unordered_map<string, int> equa2node;  
    int node_num = 0;
    int G_node_num;
    int node_map(string u) {
        if(equa2node.find(u) == equa2node.end()) {
            equa2node.insert({u, node_num});
            node_num++;
        }
        return equa2node[u];
    }                                    
    void add_edge(string u, string v, double c) {
        int a = node_map(u);
        int b = node_map(v);
        E[a].push_back((node){b, c});
        E[b].push_back((node){a, 1.0/c});
    }
    double bfs(int sou, int des) {
        if(sou == des) {
            if(sou < G_node_num) return 1.0;
            else return -1.0;
        }
        queue<node> q;
        q.push((node){sou, 1.0});
        vector<bool> vis(node_num, false);
        vis[sou] = true;
        while(!q.empty()) {
            node now = q.front();
            q.pop();
            for(auto next : E[now.to]) {
                int to = next.to;
                if(vis[to]) continue;
                vis[to] = true;
                double total_cost = now.cost*next.cost;
                if(to == des) return total_cost;
                q.push((node){to, total_cost});
            }
        }
        return -1.0;
    }                                    
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int n = values.size();
        for(int i = 0; i < n; ++i) {
            add_edge(equations[i][0], equations[i][1], values[i]);            
        }
        G_node_num = node_num;
        vector<double> ans;
        for(auto query : queries) {
            int sou = node_map(query[0]);
            int des = node_map(query[1]);
            double res = bfs(sou, des);
            ans.push_back(res);
        }
        return ans;
    }
};