C++刷leetcode（399. 除法求值）【回溯】【有向权重图】

糖逗

题目描述：

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    void dfs(double res, map<string, vector<pair<string, double> > >&store , string start, string end, string cur, double& out, map<string, int> & visit, bool & flag){
        if(store.find(cur) == store.end())return;
        if(cur == end){
            out = res;
            flag = true;
            return;
        }
        for(auto cha : store[cur]){
            if(visit[cha.first] <= 0){
                visit[cha.first]++;
                double temp = cha.second;
                string t1 = cha.first;
                res *= temp;
                dfs(res, store, start, end, cha.first, out, visit, flag);
                res /= temp;
                visit[t1]--;
            }
        }
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        map<string, vector<pair<string, double> > > store;
        for(int i = 0; i < equations.size(); i++){
            store[equations[i][0]].push_back(make_pair(equations[i][1], values[i]));
            store[equations[i][1]].push_back(make_pair(equations[i][0], 1/values[i]));
            
        }
        vector<double> res;
        for(int i = 0; i < queries.size(); i++){
            if(store.find(queries[i][1]) == store.end()) res.push_back(-1);
            else{
                double temp = 1;
                string temp1 = queries[i][0];
                string temp2 = queries[i][1];
                double out;
                map<string, int> visit;
                bool flag = false;
                dfs(temp, store, temp1, temp2, temp1, out, visit, flag);
                if(flag == false) res.push_back(-1);
                else res.push_back(out);
            } 
        }
        return res;
    }
};

注意事项：
1、使用visit记录是否访问，防止出现闭环。

糖逗