# Untitled

unknown
plain_text
a month ago
2.7 kB
0
Indexable
Never
```class Solution {
class Triple {
String destination;
double weight;

public Triple(String d, double w) {
this.destination = d;
double weight = w;
}

}

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
HashMap<String, List<Triple>> adjList = new HashMap<>();
HashMap<String, Boolean> nodes = new HashMap<>();

for (int i = 0; i < equations.size(); i++) {
String s1 = equations.get(i).get(0);
String s2 = equations.get(i).get(1);

double val = values[i];

List<Triple> sourceNode = adjList.getOrDefault(s1, new ArrayList<Triple>());

List<Triple> destNode = adjList.getOrDefault(s2, new ArrayList<Triple>());

nodes.put(s1, false);
nodes.put(s2, false);
}

HashMap<String, Boolean> visited = nodes;
double[] result = new double[queries.size()];
int i = 0;
for (List<String> list : queries) {
String s = list.get(0);
String d = list.get(1);

result[i] = -1.00;
i++;
continue;
}

if (s.equals(d)) {
result[i] = 1.00;
i++;
continue;
}

visited = nodes;
double ans = dfs(s, d, adjList, visited);

if (ans == Double.MAX_VALUE) {
result[i] = -1;
}
else {
result[i] = ans;
}
i++;
}

return result;

}

private double dfs(String source, String dest, HashMap<String, List<Triple>> adjList, HashMap<String, Boolean> visited) {

if (visited.getOrDefault(source, false)) {
return Double.MAX_VALUE;
}

visited.put(source, true);
double sum = Double.MAX_VALUE;

for (Triple t : adjList.get(source)) {
if (t.destination.equals(dest)) {
sum = t.weight;
break;
}
double val = dfs(t.destination, dest, adjList, visited);

if (val != Double.MAX_VALUE) {
sum = val * t.weight;
}
}

return sum;
}
}```