[link](https://leetcode.com/problems/path-with-maximum-probability/)

---

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

#### Example 1:


Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

#### Example 2:


Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

#### Example 3:


Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

#### Constraints:

- 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
- There is at most one edge between every two nodes.

---

Create an adjacency dictionary adj to represent the graph, where each node maps to a list of tuples containing neighbor nodes and their corresponding success probabilities. Convert the list of edges and success probabilities into the adjacency dictionary representation by iterating through the edges list and adding the corresponding neighbor node and probability to the adj dictionary for both source and destination nodes.

Initialize a max-heap maxHeap with a tuple (-1, start_node), where the negative of probability is used so that the max-heap selects the edge with the highest probability first.

Initialize an empty set visit to keep track of visited nodes. While the maxHeap is not empty:
a. Pop the tuple (prob, cur) from the maxHeap.
b. Add the current node cur to the visit set.
c. If the current node is the end_node, return the negative of prob (actual probability).
d. For each neighbor node neiNode and its corresponding edge probability EdgeProb in the adjacency dictionary for the current node:

If neiNode has not been visited, push a tuple (-1 * prob * EdgeProb, neiNode) into the max-heap. The negative of the product is used to select the edge with the maximum effective probability. If the target node end_node is not reached, return 0.

#### Solution 1

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        adj = collections.defaultdict(list)
        for i in range(len(edges)):
            adj[edges[i][0]].append((edges[i][1], succProb[i]))
            adj[edges[i][1]].append((edges[i][0], succProb[i]))
        
        maxHeap = [(-1, start_node)]
        visit = set()
        while maxHeap:
            prob, cur = heapq.heappop(maxHeap)
            visit.add(cur)
            if cur == end_node:
                return prob * -1
            for neiNode, EdgeProb in adj[cur]:
                if neiNode not in visit:
                    heapq.heappush(maxHeap, (prob * EdgeProb, neiNode))

        return 0
        

O(T): O(E*logN)
O(S): O(N + E)