Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- double dfs (unordered_map < string , vector < pair <string , double> > > &graph, string cur, string dist, double &ans, unordered_map <string, bool> &vis)
- {
- if (cur == dist)
- {
- return true;
- }
- vis[cur] = true;
- vector <pair <string , double> > vec = graph[cur];
- for (int i = 0 ; i < vec.size(); i++ )
- {
- string eq = vec[i].first;
- double w = vec[i].second;
- if (vis[eq] == false)
- {
- vis[eq] = true;
- ans *= w;
- if ( dfs (graph, eq, dist, ans, vis))
- {
- return true;
- }
- ans /= w;
- vis[eq] = false;
- }
- }
- return false;
- }
- vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
- unordered_map < string , vector < pair <string , double> > > graph;
- vector <double> res;
- int sz = equations.size();
- for (int i = 0 ; i < sz ; i++ )
- {
- string a = equations[i][0];
- string b = equations[i][1];
- double ans = values[i];
- graph[a].push_back ({b,ans});
- graph[b].push_back ({a,(1/ans)});
- }
- sz = queries.size();
- for (int i = 0 ; i <sz; i++ )
- {
- string a = queries[i][0];
- string b = queries[i][1];
- unordered_map <string, bool> vis;
- double ans = -1;
- if (graph.find(a) == graph.end() || graph.find(b) == graph.end())
- {
- res.push_back (ans);
- continue;
- }
- double dfs_ans = 1;
- bool path = dfs (graph, a, b,dfs_ans,vis);
- if (path)
- res.push_back (dfs_ans);
- else
- res.push_back (ans);
- }
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement