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

<p>Given two nodes&nbsp;<code>start</code>&nbsp;and&nbsp;<code>end</code>, find the path with the maximum probability of success to go from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>&nbsp;and return its success probability.</p>

<p>If there is no path from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>, <strong>return&nbsp;0</strong>. Your answer will be accepted if it differs from the correct answer by at most <strong>1e-5</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png" style="width: 187px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
<strong>Output:</strong> 0.25000
<strong>Explanation:</strong>&nbsp;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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png" style="width: 189px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
<strong>Output:</strong> 0.30000
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png" style="width: 215px; height: 191px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
<strong>Output:</strong> 0.00000
<strong>Explanation:</strong>&nbsp;There is no path between 0 and 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10^4</code></li>
	<li><code>0 &lt;= start, end &lt; n</code></li>
	<li><code>start != end</code></li>
	<li><code>0 &lt;= a, b &lt; n</code></li>
	<li><code>a != b</code></li>
	<li><code>0 &lt;= succProb.length == edges.length &lt;= 2*10^4</code></li>
	<li><code>0 &lt;= succProb[i] &lt;= 1</code></li>
	<li>There is at most one edge between every two nodes.</li>
</ul>

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        # succProb <=1, so extra step only decreases total prob
        # however 1x1x1 > 0.5x0.5, so we are not finding the shortest path
        
        # 2. official: Dijkstra's + Max Heap
        # step1: build the graph
        neighbors = collections.defaultdict(list)
        for i in range(len(edges)):
            a, b = edges[i]
            neighbors[a].append([b, succProb[i]])
            neighbors[b].append([a, succProb[i]])
        # step2: dijkstra
        max_prob = [0] * n  # max prob from start to each node
        max_prob[start_node] = 1
        pq = [(-1, start_node)]   # Max Heap, so use -prob
        finished = set()
        while pq:
            cur_prob, cur_node = heapq.heappop(pq)
            finished.add(cur_node)
            if cur_node == end_node:
                return -cur_prob
            # Update paths from start to unfinished neighbors of cur_node via cur_node        
            for nxt_node, prob in neighbors[cur_node]:
                if nxt_node not in finished:
                    if -cur_prob * prob > max_prob[nxt_node]:
                        max_prob[nxt_node] = -cur_prob * prob
                        heapq.heappush(pq, (-max_prob[nxt_node], nxt_node))
                
        return 0
        
        # 1. [WRONG ANS! why?]My Approach: DFS + Memo
        # Example: 
        # edges =[[0,1], [1,2], [1,3], [2,3], [0,2]]
        # succProb = [0.001, 1, 0.1, 0.001, 1], start=0, end=3
        # memo[2] will be 0.001, but largest path has 0.1 (2->1->3)
        # Reason: the best way from 2 to 3 is via 1, but the path has already visited 1, it won't revisit it, so we miss this path 
        # find all paths, don't recompute subproblems
        # max_prob from cur to end = succProb(cur, neighbor) * max prob among all neighbor to end
        # memo[i] = maxProb from i to end_node
        # hint: multiplying probabilities will result in precision errors
        # => Take log probabilities to sum up numbers instead of multiplying them
        neighbors = collections.defaultdict(list)
        for i in range(len(edges)):
            a, b = edges[i]
            neighbors[a].append([b, succProb[i]])
            neighbors[b].append([a, succProb[i]])

        memo = dict()
        visited = set()     # don't revisit on each path
        def dfs(cur_node):
            """
            return the maxProb from cur_node to end_node
            """
            nonlocal neighbors, visited, end_node
            if cur_node == end_node:
                # return math.log(1)
                return 1
            if cur_node in memo:
                return memo[cur_node]

            # try all neighbors, except ones already visited on current path
            max_prob = float("-inf")
            for neighbor, succProb in neighbors[cur_node]:
                if neighbor in visited:
                    continue
                visited.add(neighbor)
                # max_prob = max(max_prob, math.log(succProb) + dfs(neighbor))
                max_prob = max(max_prob, succProb * dfs(neighbor))

                visited.remove(neighbor)        # Backtrack
            memo[cur_node] = max_prob
            return max_prob

        

        log_prob = dfs(start_node)
        if log_prob == float("-inf"):
            return 0
        else:
            # return exp(log_prob)
            return log_prob
                    
28300