题目描述

给你一个由 n 个结点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接结点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i]。

指定两个结点分别作为起点 start 和终点 end，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0。只要答案与标准答案的误差不超过 1e-5，就会被视作正确答案。

样例

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2，而另一条为 0.5 * 0.5 = 0.25。

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：结点 0 和 结点 2 之间不存在路径。

限制

• 2 <= n <= 10^4
• 0 <= start, end < n
• start != end
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• 每两个结点之间最多有一条边。

算法

(最短路) $O((n + m) \log n)$

1. 最短路模板题，采用堆优化的 Dijkstra，边权累计方式改为乘积，求最长路。
2. 由于求最长路且代价为乘积累计的方式，这相当于取负对数后的最短路。

时间复杂度

• 堆优化 Dijkstra 的时间复杂度为 $O((n + m) \log n)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储图和最短路相关的数据结构。

C++ 代码

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges,
                          vector<double>& succProb, int start, int end) {
        int m = edges.size();
        vector<vector<pair<int, double>>> graph(n);

        for (int i = 0; i < m; i++) {
            int x = edges[i][0], y = edges[i][1];
            double s = succProb[i];
            graph[x].emplace_back(y, s);
            graph[y].emplace_back(x, s);
        }

        priority_queue<pair<double, int>> q;
        vector<double> dis(n, 0);
        vector<bool> vis(n, false);

        dis[start] = 1.0;
        q.push(make_pair(1.0, start));

        while (!q.empty()) {
            auto cur = q.top();
            q.pop();

            if (end == cur.second)
                return dis[end];

            if (vis[cur.second]) continue;
            vis[cur.second] = true;

            for (const auto &t : graph[cur.second])
                if (dis[t.first] < cur.first * t.second) {
                    dis[t.first] = cur.first * t.second;
                    q.push(make_pair(dis[t.first], t.first));
                }
        }

        return dis[end];
    }
};