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
33
34
35
36
37
38
39
40
41
42
43
44
45
| class {
private:
bool dfs(unordered_map<string, unordered_map<string, double> > &m,
string startvalue, string endvalue, unordered_map<string,bool> &visited, double & res) {
if (m.find(startvalue) == m.end() || m.find(endvalue) == m.end()) { return false;}
if (startvalue == endvalue) { return true; }
for (auto iter = m[startvalue].begin(); iter != m[startvalue].end(); iter++) {
if (visited.find(iter->first) != visited.end()) { continue; }
visited[iter->first] = true;
double old = res;
res *= m[startvalue][iter->first];
if (dfs(m, iter->first, endvalue, visited, res)) { return true; }
visited.erase(iter->first);
res = old;
}
return false;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> result;
unordered_map<string, unordered_map<string, double> > m;
for (int i = 0; i < equations.size();i++) {
string first = equations[i].first;
string second = equations[i].second;
m[first][second] = values[i];
m[second][first] = 1.0 / values[i];
}
for (int i = 0; i < queries.size(); i++) {
string start = queries[i].first;
string end = queries[i].second;
double res = 1.0;
unordered_map<string, bool> visited;
visited[start] = true;
if (dfs(m, start, end, visited, res)) { result.push_back(res);}
else { result.push_back(-1.0);}
}
return result;
}
};
|
