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的情况，且不存在任何矛盾的结果。
class Solution { public: typedef struct Node{ string v; double w; Node(){} Node(string a, double b):v(a), w(b){} }node; unordered_map<string, double> dijkstra(unordered_map<string, vector<node>> &G, string s){ unordered_map<string, int>vis; unordered_map<string, double>dis; for(unordered_map<string, vector<node>>::iterator it = G.begin(); it != G.end();it++){ vis[it->first] = 0; dis[it->first] = INT_MAX; } dis[s] = 1; for(int i = 0;i < dis.size();i++){ double mmin = INT_MAX; string u = ""; for(unordered_map<string, double>::iterator it = dis.begin(); it != dis.end();it++){ if(vis[it->first] == 0 && mmin > it->second){ mmin = it->second; u = it->first; } } if(u.size() == 0) return dis; vis[u] = 1; for(int i = 0;i < G[u].size();i++){ string tempv = G[u][i].v; double tempw = G[u][i].w; if(vis[tempv] == 0 && dis[tempv] > dis[u] * tempw) dis[tempv] = dis[u] * tempw; } } return dis; } vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { vector<double>results; unordered_map<string, vector<node>>G; unordered_map<string, unordered_map<string, double>> dis; for(int i = 0;i < equations.size();i++){ G[equations[i][0]].push_back(Node(equations[i][1], values[i])); G[equations[i][1]].push_back(Node(equations[i][0], 1.0/values[i])); } for(unordered_map<string, vector<node>>::iterator it = G.begin(); it != G.end();it++){ unordered_map<string, double> temp = dijkstra(G, it->first); dis[it->first] = temp; } for(int i = 0;i < queries.size();i++){ if(dis[queries[i][0]].count(queries[i][1]) != 0 && dis.count(queries[i][0]) != 0) if(dis[queries[i][0]][queries[i][1]] == INT_MAX) results.push_back(-1.0); else results.push_back(dis[queries[i][0]][queries[i][1]]); else results.push_back(-1.0); } return results; } };解题思路：可以把这个看成一个图的题目 a / b = 2描述成a -> b的权值为2，相反知道 a / b = 2, 则肯定是知道 b / a的值的， 则有 b -> a 权值为0.5的边，通过遍历equations这个数组来构建我们的有向图，因为是用字符来描述节点所以用的是unordered_map来做一个邻接表的作用，遍历的时候和数组一样直接用迭代器遍历就好了，构建完图之后是求表达式，首先要判断的是要求的这个表达式中的两个变量是否都出现在了equations这个数组里面，不在的话直接返回-1.0就好了，然后对你构建好的图进行map.size()次迪杰斯特拉，其中注意的是a / b 和 b / c得到a / c不是简单的相加而是相乘的结果，所以dis[v] = min(dis[v],dis[u] * w)，而相对应的起点的dis[s]初始值应该设为1。额外的内存用的比较多，所以时间复杂度相对比较低一点。
