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


  • 0
    G

    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;
        }
    };
    

Log in to reply
 

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