剑指 Offer II 111. 计算除法

399. 除法求值

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<double> r;
        //转换成图: 一维是起始索引，二维是pair{终止节点，权重}
        vector<vector<pair<int, double>>> graph;
        unordered_map<string, int> m;
        int n = buildGraph(equations, values, m, graph);
        
        for (auto& v : queries)
        {
            if (!m.count(v[0]) || !m.count(v[1]))
            {
                r.push_back(-1.0);
            }
            else
            {
                r.push_back(dijkstra(n, m[v[0]], m[v[1]], graph));
            }            
        }

        return r;
    }

    int buildGraph(vector<vector<string>>& equations, vector<double>& values, unordered_map<string, int>& m, vector<vector<pair<int, double>>>& graph)
    {
        static int index = 0;
        int n = equations.size();
        graph.resize(2*n);

        for (int i=0;i<n;++i)
        {
            if (!m.count(equations[i][0]))
            {
                m.insert({equations[i][0], index++});
            }

            if (!m.count(equations[i][1]))
            {
                m.insert({equations[i][1], index++});
            }

            graph[m[equations[i][0]]].push_back({m[equations[i][0]], 1.0});
            graph[m[equations[i][0]]].push_back({m[equations[i][1]], values[i]});
            
            graph[m[equations[i][1]]].push_back({m[equations[i][1]], 1.0});
            graph[m[equations[i][1]]].push_back({m[equations[i][0]], 1.0 / values[i]});
        }

        return index;
    }

	//graph是图的邻接边实现，第一维是起点，二维是<终点、开销>
    //为了避免图中有孤立的节点，建议传入图中节点的数量
	double dijkstra(int n, int start, int end, vector<vector<pair<int, double>>>& graph)
	{          
		// 定义：distTo[i] 的值就是起点 start 到达节点 i 的最小权重
		vector<double> distTo(n, INT_MAX);
		// base case，start 到 start 的最小权重
		distTo[start] = 1.0;

		// 优先级队列，distFromStart 较小的排在前面
		struct cmp
		{
			//[0]: 当前节点, [1]: 从start到达当前节点的最小概率
			bool operator () (const pair<int, double>& a, const pair<int, double>& b)
			{
				return a.second > b.second;
			}
		};

		//构建基于权重的最小堆
		priority_queue<pair<int, double>, vector<pair<int, double>>, cmp> minHeap;
		// 从起点 start 开始进行 BFS
		minHeap.push(make_pair(start, 1.0));

		while (!minHeap.empty())
		{
			auto currNode = minHeap.top();
			minHeap.pop();
			int curNodeID = currNode.first;
			if (curNodeID == end)
				return distTo[curNodeID];

			// 将 curNode 的相邻节点装入队列
			for (auto& neighbor : graph[curNodeID])
			{
				int nextNodeID = neighbor.first;
				// int distToNextNode = distTo[curNodeID] + neighbor.second;
				double distToNextNode = distTo[curNodeID] * neighbor.second;

				if (distTo[nextNodeID] > distToNextNode)
				{
					distTo[nextNodeID] = distToNextNode;
					minHeap.push(make_pair(nextNodeID, distToNextNode));
				}
			}
		}

		return (int)distTo[end] == INT_MAX ? -1.0 : distTo[end];
	}    
};