1514. Path with Maximum Probability =================================== 题目信息 -------- :题号: 1514 :难度: Medium :主题: 图、最短路变体、优先队列、概率乘积 :原题: `LeetCode 1514 `_ :重点: 无向边的成功概率沿路径相乘;寻找从起点到终点乘积最大的路径,不可达时返回 ``0`` 题目重述 -------- 给定含 ``n`` 个节点的无向图,节点编号为 ``0`` 到 ``n-1``。``edges[i]`` 的两个端点之间存在一条边,沿该边成功通过的概率为 ``succProb[i]``。 一条路径的成功概率等于路径上所有边概率的乘积。请返回从 ``start_node`` 到 ``end_node`` 的最大成功概率;若终点不可达,返回 ``0``。 ``2 <= n <= 10^4``,边数不超过 ``2 * 10^4``,每个概率位于 ``[0,1]``。 自建示例 -------- 更多边的路径可能拥有更高乘积: .. code-block:: text 输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start_node = 0, end_node = 2 输出:0.25 解释:路径 0 -> 1 -> 2 的概率为 0.5 * 0.5 = 0.25,高于直接边的 0.2。 终点不连通时概率为零: .. code-block:: text 输入:n = 3, edges = [[0,1]], succProb = [0.9], start_node = 0, end_node = 2 输出:0.0 解释:不存在从节点 0 到节点 2 的路径。