P1079 概率最大的路径
概率最大的路径
题目描述
给你一个由 个节点(下标从 开始)组成的无向加权图,该图由一个描述边的列表组成,其中 表示连接节点 和 的一条无向边,且该边遍历成功的概率为 。
指定两个节点分别作为起点 和终点 ,请你找出从起点到终点 成功概率最大的路径,并返回其成功概率。
如果不存在从 到 的路径,请返回 。
给你一个由 n 个节点(下标从 0 开始)组成的无向加权图,该图由一个描述边的列表组成,其中 edges[i]=[a,b] 表示连接节点 a 和 b 的一条无向边,且该边遍历成功的概率为 succProb[i]。
指定两个节点分别作为起点 start 和终点 end,请你找出从起点到终点 成功概率最大的路径,并返回其成功概率。
如果不存在从 start 到 end 的路径,请返回 0。