原题链接
Floyd 算法,求两点间的最短路径的一种算法。
把两个字母看做图的节点,把两个字母相除的商看做两个点之间的路径权值。问题是求给定两点之间是否有路径,并计算出权值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : vector<double > calcEquation (vector<vector<string>>& equations, vector<double >& values, vector<vector<string>>& queries) { unordered_set<string> vers; unordered_map<string, unordered_map<string, double >> d; for (int i=0 ;i<equations.size ();i++) { auto a = equations[i][0 ], b=equations[i][1 ]; auto c = values[i]; d[a][b] = c, d[b][a] = 1 /c; vers.insert (a); vers.insert (b); } for (auto k: vers) { for (auto i: vers) { for (auto j: vers) { if (d[i][k] && d[j][k]) { d[i][j] = d[i][k] * d[k][j]; } } } } vector<double > res; for (auto q: queries) { auto a = q[0 ], b = q[1 ]; if (d[a][b]) res.push_back (d[a][b]); else res.push_back (-1 ); } return res; } };