Path With Maximum Probability

Given an undirected graph with success probabilities on edges, return the maximum probability of reaching the destination from the start. Pattern focus: Dijkstra. Use a max-priority queue or an equivalent transformation so higher-probability states are expanded first.

Input Format

n = node count, edges = undirected edges, succProb = edge probabilities, start = source, end = destination

Output Format

maximum success probability from start to end

Constraints

• 2 <= n <= 10^4
• 1 <= edges.length <= 2 * 10^4
• 0 <= succProb[i] <= 1

Examples

n = 3
edges = [[0,1],[1,2],[0,2]]
succProb = [0.5,0.5,0.2]
start = 0
end = 2

0.25

n = 3
edges = [[0,1]]
succProb = [0.7]
start = 0
end = 1

0.7

n = 3
edges = [[0,1]]
succProb = [0.7]
start = 0
end = 2

0.0