# Clean "Floyd" method in C++. Easy to understand.

• We can think of this problem as a graph problem. "a / b = 2.0" means from point a to point b there is an edge, and its weight is 2.0. So the question is, given a query "e / f", we need to check whether e and f are connected. If yes, calculate the value, otherwise return -1. Thus, we can use Floyd method in graph to solve it.

``````class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string, int> points; // mapping from string to points index
int idx = 0;
for (const auto& e : equations) {
if (points.find(e.first) == points.end())
points.emplace(e.first, idx++);
if (points.find(e.second) == points.end())
points.emplace(e.second, idx++);
}

// Floyd initializate
vector<vector<double>> graph(points.size(), vector<double>(points.size(), INT_MAX));
for (int i = 0; i < equations.size(); i++) {
int idx_a = points[equations[i].first];
int idx_b = points[equations[i].second];
graph[idx_a][idx_a] = 1.0;
graph[idx_b][idx_b] = 1.0;
graph[idx_a][idx_b] = values[i];
graph[idx_b][idx_a] = 1.0 / values[i];
}

// Floyd update
for (int k = 0; k < points.size(); k++) {
for (int i = 0; i < points.size(); i++) {
for (int j = 0; j < points.size(); j++) {
if (graph[i][k] != INT_MAX
&& graph[k][j] != INT_MAX
&& graph[i][k] * graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] * graph[k][j];
}
}
}

// Calculate
vector<double> results;
for (const auto q : queries) {
if (points.find(q.first) == points.end() || points.find(q.second) == points.end()) {
results.push_back(-1.0);
} else {
int idx_a = points[q.first];
int idx_b = points[q.second];
double distance = graph[idx_a][idx_b] == INT_MAX ? -1.0 : graph[idx_a][idx_b];
results.push_back(distance);
}
}

return results;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.