Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example: Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            if (!graph.containsKey(equations.get(i).get(0)))
                graph.put(equations.get(i).get(0), new HashMap<>());
            graph.get(equations.get(i).get(0)).put(equations.get(i).get(1), values[i]);
            if (!graph.containsKey(equations.get(i).get(1)))
                graph.put(equations.get(i).get(1), new HashMap<>());
            graph.get(equations.get(i).get(1)).put(equations.get(i).get(0), (double) (1 / values[i]));
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = getPath(graph, queries.get(i).get(0), queries.get(i).get(1));
        }
        return ans;
    }

    public double getPath(HashMap<String, HashMap<String, Double>> graph, String src, String dst) {
        if (!graph.containsKey(src) || !graph.containsKey(dst))
            return -1.0;
        Set<String> visited = new HashSet<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(src, 1));
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                Pair node = q.poll();
                if (visited.contains(node.str))
                    continue;
                visited.add(node.str);
                if (dst.equals(node.str))
                    return node.value;
                for (String neighbor : graph.get(node.str).keySet())
                    q.add(new Pair(neighbor, node.value * graph.get(node.str).get(neighbor)));
            }
        }
        return -1.0;
    }

    static class Pair {
        String str;
        double value;

        Pair(String str, double v) {
            this.str = str;
            value = v;
        }
    }
}