原题链接

Floyd 算法，求两点间的最短路径的一种算法。

把两个字母看做图的节点，把两个字母相除的商看做两个点之间的路径权值。问题是求给定两点之间是否有路径，并计算出权值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_set<string> vers;
        unordered_map<string, unordered_map<string, double>> d;

        for(int i=0;i<equations.size();i++) {
            auto a = equations[i][0], b=equations[i][1];
            auto c = values[i];
            d[a][b] = c, d[b][a] = 1/c;
            vers.insert(a);
            vers.insert(b);

        }
        for(auto k: vers) {
            for(auto i: vers) {
                for(auto j: vers) {
                    if(d[i][k] && d[j][k]) {
                        d[i][j] = d[i][k] * d[k][j];
                    }
                }
            }
        }
        vector<double> res;
        for(auto q: queries) {
            auto a = q[0], b = q[1];
            if(d[a][b]) res.push_back(d[a][b]);
            else res.push_back(-1);
        }
        return res;
    }
};