0399.cpp (1583B)
1 class Solution { 2 const int SIZE = 26 * 5; 3 4 int hash(const string &st) { 5 static int index = 0; 6 static unordered_map<string, int> um; 7 if (!um.count(st)) um[st] = index++; 8 return um[st]; 9 } 10 11 double dfs(vector<vector<pair<int, double>>> &adj, int start, int goal) { 12 stack<pair<int, double>> st; 13 vector<bool> visited(SIZE, false); 14 15 st.push({start, 1}); 16 visited[start] = true; 17 while (!st.empty()) { 18 auto [root, value] = st.top(); 19 st.pop(); 20 if (root == goal) return value; 21 visited[root] = true; 22 for (auto &v : adj[root]) 23 if (!visited[v.first]) st.push({v.first, value * v.second}); 24 } 25 return -1; 26 } 27 28 public: 29 vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, 30 vector<vector<string>> &queries) { 31 vector<vector<pair<int, double>>> adj(SIZE, vector<pair<int, double>>()); 32 for (int i = 0; i < values.size(); i++) { 33 adj[hash(equations[i][0])].push_back({hash(equations[i][1]), values[i]}); 34 adj[hash(equations[i][1])].push_back({hash(equations[i][0]), 1 / values[i]}); 35 } 36 37 vector<double> res(queries.size(), -1); 38 for (int i = 0; i < queries.size(); i++) { 39 int start = hash(queries[i][0]), goal = hash(queries[i][1]); 40 if (adj[start].empty() || adj[goal].empty()) continue; 41 res[i] = dfs(adj, start, goal); 42 } 43 return res; 44 } 45 };