剑指 Offer II 111. 计算除法 （先用floyd算法预处理最短路径）

直接用floyd处理最短路径，然后直接输出最短路径的值即可。其中使用C++ unordered_map存图技巧。

class Solution {
public:
    vector calcEquation(vector>& equations, vector& values, vector>& queries) {
        unordered_set vertex;
        unordered_map> distance;
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            distance[equations[i][0]][equations[i][1]] = values[i];
            distance[equations[i][1]][equations[i][0]] = 1.0 / values[i]; 
            vertex.insert(equations[i][0]);
            vertex.insert(equations[i][1]);
        }

        for (auto k : vertex) {
            for (auto i : vertex) {
                for (auto j : vertex) {
                    if (distance[i][k] && distance[k][j]) {
                        distance[i][j] = distance[i][k] * distance[k][j];
                    }
                }
            }
        }

        vector res;
        for (auto query : queries) {
            if (distance[query[0]][query[1]]) {
                res.push_back(distance[query[0]][query[1]]);
            } else {
                res.push_back(-1.0);
            }
        }
        return res;
    }
};