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.

Difficulty: interview

Starter code:

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        

Solutions:
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], probs: List[float], s: int, t: int) -> float:
        # first build the graph
        graph = {u: {} for u in range(n)}
        for (u, v), prob in zip(edges, probs):
            graph[u][v] = prob
            graph[v][u] = prob

        # run A* search
        frontier = [(-1, s)]
        seen = set()

        while len(frontier) != 0:
            neg_path_prob, u = heapq.heappop(frontier)
            if u == t:
                return -neg_path_prob

            seen.add(u)
            for v, edge_prob in graph[u].items():
                if v not in seen:
                    heapq.heappush(frontier, (neg_path_prob * edge_prob, v))
        return 0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = collections.defaultdict(dict)
        for edge, prob in zip(edges, succProb):
            s, t = edge
            graph[s][t] = prob
            graph[t][s] = prob
        
        heap = [(-1, start)]
        prob = [0] * n
        prob[start] = 1
        visited = [False] * n
        
        while heap:
            curr_prob, node = heapq.heappop(heap)
            if visited[node]:
                continue
            if node == end:
                return prob[end]
            curr_prob *= -1
            visited[node] = True
            for neighbor in graph[node]:
                if visited[neighbor]:
                    continue
                p = curr_prob * graph[node][neighbor]
                if p > prob[neighbor]:
                    prob[neighbor] = p
                    heapq.heappush(heap, (-p, neighbor))
        
        return prob[end]

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        weights = list(map(lambda x:-math.log2(x), succProb))
        g = defaultdict(list)
        for (u, v), w in zip(edges, weights):
            g[u].append([v, w])
            g[v].append([u, w])
        dist = {}
        q = [(0, start)]
        while q:
            w, u = heapq.heappop(q)
            if u in dist:
                continue
            dist[u] = w
            if u == end:
                break
            for v, w in g[u]:
                if v not in dist or dist[v] > dist[u] + w:
                    heapq.heappush(q, (dist[u] + w, v))
        return 2 ** (-dist[end]) if end in dist else 0.0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        # bfs only when prob is less than cur best add to the queue
        graph = [[] for _ in range(n)]
        for edge, p in zip(edges, succProb):
            a, b = edge
            graph[a].append((b, p))
            graph[b].append((a, p))
        prob = {start: 1}
        queue = [(start, 1)]
        while queue:
            new_queue = []
            for a, p_a in queue:
                for b, p_b in graph[a]:
                    p = p_a*p_b
                    if b not in prob or p > prob[b]:
                        prob[b] = p
                        new_queue.append((b, p))
            # print(prob)
            queue = new_queue
        return prob.get(end, 0)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], prob: List[float], start: int, end: int) -> float:
        weights = list(map(lambda x:-math.log2(x), prob))
        g = defaultdict(list)
        
    
        for (u, v), w in zip(edges, weights):
            g[u].append([v, w])
            g[v].append([u, w])
        dist = {}
        q = [(0, start)]
        while q:
            w, u = heapq.heappop(q)
            if u in dist:
                continue
            dist[u] = w
            if u == end:
                break
            for v, w in g[u]:
                if v not in dist or dist[v] > dist[u] + w:
                    heapq.heappush(q, (dist[u] + w, v))
        return 2 ** (-dist[end]) if end in dist else 0.0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = defaultdict(list)
        
        for (a, b), probability in zip(edges, succProb):
            graph[a].append([b, probability])
            graph[b].append([a, probability])
        
        if start == end:
            return 1
        
        queue = [[-1, start]]
        visited = set()
        distance_map = defaultdict(lambda: float('inf'))
        
        while queue:
            prob, node = heappop(queue)
            
            visited.add(node)
            
            if node == end:
                return -prob
            
            for neighbour, next_prob in graph[node]:
                if neighbour in visited:
                    continue
                heappush(queue, [prob * next_prob, neighbour])
        
        return 0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dp = [0.0 for _ in range(start)]+[1.0]+[0.0 for _ in range(start+1,n)]
        dic = defaultdict(list)
        for e,p in zip(edges, succProb):
            dic[e[0]].append((e[1],p))
            dic[e[1]].append((e[0],p))
        
        queue = deque([start])
        while queue:
            for _ in range(len(queue)):
                cur = queue.popleft()
                for c,p in dic[cur]:
                    if dp[cur]*p > dp[c]:
                        dp[c] = dp[cur]*p
                        queue.append(c)
        return dp[end]

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], prob: List[float], start: int, end: int) -> float:
        weights = list([-math.log2(x) for x in prob])
        g = defaultdict(list)
        for (u, v), w in zip(edges, weights):
            g[u].append([v, w])
            g[v].append([u, w])
        dist = {}
        q = [(0, start)]
        while q:
            w, u = heapq.heappop(q)
            if u in dist:
                continue
            dist[u] = w
            if u == end:
                break
            for v, w in g[u]:
                if v not in dist or dist[v] > dist[u] + w:
                    heapq.heappush(q, (dist[u] + w, v))
        return 2 ** (-dist[end]) if end in dist else 0.0
                
                
            
            
            


from heapq import heappop, heappush
from sys import maxsize as inf
from collections import defaultdict as dic

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = dic(dict)

        for [u, v], w in zip(edges,succProb):
            graph[u][v] = w
            graph[v][u] = w

        dist = { i : 0 for i in range(n)}
        dist[start] = 1
        visited = set()
        max_prob = [(-1*1,start)]
        while len(max_prob):
            cur_prob, cur_node = heappop(max_prob)
            if cur_node in visited:
                continue
            visited.add(cur_node)
            for nei in graph[cur_node]:
                if nei in visited:
                    continue
                if dist[nei] < graph[cur_node][nei] * (-1*cur_prob):
                    dist[nei] = graph[cur_node][nei] * (-1*cur_prob)
                    heappush(max_prob, ((-1*dist[nei]),nei) )
                    
            if cur_node == end:
                break

        return(dist[end])


from collections import defaultdict as ddict
from collections import deque
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        maxProb = ddict(float)
        
        graph = ddict(dict)
        
        for [a,b],sucprob in zip(edges, succProb):
            graph[a][b] = sucprob if b not in graph[a] else max(sucprob, graph[a][b])
            graph[b][a] = sucprob if a not in graph[b] else max(sucprob, graph[b][a])
        
        print(graph)
        
        que = deque()
        que.append((start, 1))
        while que:
            node, prob = que.popleft()
            maxProb[node] = max(maxProb[node], prob)
            
            for child in graph[node]:
                if prob*graph[node][child] > maxProb[child]:
                    que.append((child, prob*graph[node][child]))
        
        
        return maxProb[end]


from heapq import heappush, heappop


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        stack = [(-1, start)]
        paths = [0 for i in range(n)]
        paths[start] = 1
        
        graph = [{} for i in range(n)]
        for (source, dstn), weight in zip(edges, succProb):
            graph[source][dstn] = graph[dstn][source] = weight
        while stack:
            _, current = heappop(stack)
            for v in graph[current]:
                temp = paths[current] * graph[current][v]
                if temp > paths[v]:
                    heappush(stack, (-temp, v))
                    paths[v] = max(temp, paths[v])
        return paths[end] 


import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        adj = {i:[] for i in range(n)}
        best = [0] * n   
        
        for edge, prob in zip(edges, succProb):
            u, v = edge
            adj[u].append((v, prob))
            adj[v].append((u, prob))
            
        queue = []
        heapq.heappush(queue, (-1, start))
        while queue:
            prob, v = heapq.heappop(queue)
            prob = - prob
            if v == end:
                return prob
            if prob < best[v]:
                continue
            best[v] = prob
            for nxt, np in adj[v]:
                if nxt != v:
                    tmp = np * prob
                    if tmp > best[nxt]:
                        best[nxt] = tmp
                        heapq.heappush( queue, (-tmp, nxt) )
        
        return 0
                    


import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        adj = {i:[] for i in range(n)}
        best = [0] * n   
        
        for edge, prob in zip(edges, succProb):
            u, v = edge
            adj[u].append((v, prob))
            adj[v].append((u, prob))
            
        queue = []
        heapq.heappush(queue, (-1, start))
        best[start] = 1
        while queue:
            prob, v = heapq.heappop(queue)
            prob = - prob
            if v == end:
                return prob
            if prob < best[v]:
                continue
            for nxt, np in adj[v]:
                if nxt != v:
                    tmp = np * prob
                    if tmp > best[nxt]:
                        best[nxt] = tmp
                        heapq.heappush( queue, (-tmp, nxt) )
        
        return 0
                    


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dp = [0.0 for _ in range(start)] + [1.0] + [0.0 for _ in range(start+1,n)]
        # dp[i] is the prob of getting node i from node start
        
        graph = defaultdict(list)
        for (u,v),p in zip(edges,succProb):
            graph[u].append((v,p))
            graph[v].append((u,p))
        
        # dijkstra's algorithm
        selected = set()
        heap = [(-1.0, start)]
        
        while heap:
            p, cur = heapq.heappop(heap)
            selected.add(cur)
            if cur==end:
                return -p
            for child, prob in graph[cur]:
                if child not in selected and dp[cur]*prob>dp[child]:
                    dp[child] = dp[cur]*prob
                    heapq.heappush(heap, (-dp[child],child))
        return 0

import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        adj = {i:[] for i in range(n)}
        best = [0] * n   
        
        for edge, prob in zip(edges, succProb):
            u, v = edge
            adj[u].append((v, prob))
            adj[v].append((u, prob))
            
        queue = []
        heapq.heappush(queue, (-1, start))
        best[start] = 1
        while queue:
            prob, v = heapq.heappop(queue)
            prob = - prob
            if v == end:
                return prob
            if prob < best[v]:
                continue
            best[v] = prob
            for nxt, np in adj[v]:
                if nxt != v:
                    tmp = np * prob
                    if tmp > best[nxt]:
                        best[nxt] = tmp
                        heapq.heappush( queue, (-tmp, nxt) )
        
        return 0
                    


from collections import defaultdict, deque


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        stack = deque([start])
        paths = [0 for i in range(n)]
        paths[start] = 1
        
        graph = [{} for i in range(n)]
        for (source, dstn), weight in zip(edges, succProb):
            graph[source][dstn] = graph[dstn][source] = weight
        # seen = set()
        while stack:
            current = stack.popleft()
            for v in graph[current]:
                temp = paths[current] * graph[current][v]
                if temp > paths[v]:
                    stack.append(v)
                    paths[v] = max(temp, paths[v])
        return paths[end] 


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], prob: List[float], start: int, end: int) -> float:
        weights = list(map(lambda x:-math.log2(x), prob))
        g = defaultdict(list)
        for (u, v), w in zip(edges, weights):
            g[u].append([v, w])
            g[v].append([u, w])
        dist = {}
        q = [(0, start)]
        while q:
            w, u = heapq.heappop(q)
            if u in dist:
                continue
            dist[u] = w
            if u == end:
                break
            for v, w in g[u]:
                if v not in dist or dist[v] > dist[u] + w:
                    heapq.heappush(q, (dist[u] + w, v))
        return 2 ** (-dist[end]) if end in dist else 0.0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        def method1():
            graph=collections.defaultdict(set)
            for i,pair in enumerate(edges):
                u,v=pair
                graph[u].add((v,succProb[i]))
                graph[v].add((u,succProb[i]))
                
            seen={0:0}
            queue=[(start,-1)]
            ans=float('-inf')
            while queue:
                node,p=heapq.heappop(queue)
                p=-p
                if node==end:
                    ans=max(ans,p)
                for nei,dw in graph[node]:
                    if (nei not in seen or seen[nei]<p*dw) and p*dw>ans:
                        seen[nei]=p*dw
                        heapq.heappush(queue,(nei,-p*dw))
                        
            return ans if ans!=float('-inf') else 0
        
        #return method1()
    
        def method2():
            AdjList = [set() for _ in range(n)]
            
            for (u, v), p in zip(edges, succProb):
                AdjList[u].add((v, log2(1/p)))
                AdjList[v].add((u, log2(1/p)))
            
            dist = [float('inf') for _ in range(n)]
            dist[start] = 0
            h = [(0, start)]
            while h:
                d, u = heappop(h)
                if d == dist[u]:
                    for (v, p) in AdjList[u]:
                        if dist[u] + p < dist[v]:
                            dist[v] = dist[u] + p
                            heappush(h, (dist[v], v))
            return 1 / (2 ** dist[end])
        return method2()

from collections import defaultdict, deque
import bisect
from sortedcontainers import SortedList


# class Solution:
#     def maxProbability(self, n: int, edges, succProb, start: int, end: int) -> float:

#         m = [{} for i in range(n)]
#         for edge, d in zip(edges, succProb):
#             s, e = edge
#             m[s][e] = m[e][s] = d

#         seen = {start: 1}       
#         sorted_e = SortedList([m[start][k], k] for k in m[start])
        
#         while sorted_e:
            
#             if end in seen: break        
#             p, e = sorted_e.pop()
#             seen[e] = p
    
#             for tmp_e, tmp_p in m[e].items():
#                 if tmp_e in seen: continue
#                 new_p = tmp_p * p
#                 sorted_e.add([new_p, tmp_e])
        
#         return seen.get(end, 0)

class Solution:
    def maxProbability(self, n: int, edges, succProb, start: int, end: int) -> float:

        m = [{} for i in range(n)]
        for edge, d in zip(edges, succProb):
            s, e = edge
            m[s][e] = m[e][s] = d

        queue = deque([start])
        seen = [0] * n
        seen[start] = 1

        while queue:

            s = queue.popleft()
            prob = seen[s]

            for e, p in m[s].items():
                tmp = prob * p
                if seen[e] < tmp:
                    seen[e] = tmp
                    queue.append(e)

        return seen[end]

from heapq import heappush, heappop
from math import log2

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        AdjList = [set() for _ in range(n)]
        for (u, v), p in zip(edges, succProb):
            AdjList[u].add((v, log2(1/p)))
            AdjList[v].add((u, log2(1/p)))
        dist = [float('inf') for _ in range(n)]
        dist[start] = 0
        h = [(0, start)]
        while h:
            d, u = heappop(h)
            if True:
                for (v, p) in AdjList[u]:
                    if dist[u] + p < dist[v]:
                        dist[v] = dist[u] + p
                        heappush(h, (dist[v], v))
        return 1 / (2 ** dist[end])

class Solution:
    def maxProbability(self, n, edges, succProb, start, end) -> float:
        
        g    = [[] for _ in range(n)]
        prob = [0.  for _ in range(n)]
        
        prob[start] = 1.
        
        for (a,b), p in zip(edges, succProb):
            g[a].append((p, b))
            g[b].append((p, a))
        
        pq = [(-1., start)]
        
        while pq:
            p, v = heapq.heappop(pq)
            if prob[v] + p: continue
            
            if v == end:
                return prob[v]
            
            for ep, n in g[v]:
                _p = ep * prob[v]
                
                if _p > prob[n]:
                    prob[n] = _p
                    heapq.heappush(pq, (-_p, n))
        
        return 0
            
            
            


from collections import defaultdict, deque


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        stack = deque([start])
        paths = {i: 0 for i in range(n)}
        paths[start] = 1
        
        graph = {i: {} for i in range(n)}
        for (source, dstn), weight in zip(edges, succProb):
            graph[source][dstn] = graph[dstn][source] = weight

        while stack:
            current = stack.popleft()
            for v in graph[current]:
                if paths[current] * graph[current][v] > paths[v]:
                    stack.append(v)
                    paths[v] = max(paths[current] * graph[current][v], paths[v])
        return paths[end] 


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], probs: List[float], s: int, t: int) -> float:
        # first build the graph
        graph = {u: {} for u in range(n)}
        for (u, v), prob in zip(edges, probs):
            graph[u][v] = prob
            graph[v][u] = prob

        # run DFS/BFS search
        frontier = [s]
        path_probs = {u: 0 for u in range(n)}
        path_probs[s] = 1

        while len(frontier) != 0:
            u = frontier.pop(0)
            path_prob = path_probs[u]

            for v, edge_prob in graph[u].items():
                if path_prob * edge_prob > path_probs[v]:
                    path_probs[v] = path_prob * edge_prob
                    frontier.append(v)
        return path_probs[t]

from collections import defaultdict, deque


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        stack = deque([start])
        paths = {i: 0 for i in range(n)}
        paths[start] = 1
        
        graph = defaultdict(dict)
        for (source, dstn), weight in zip(edges, succProb):
            graph[source][dstn] = weight
            graph[dstn][source] = weight

        while stack:
            current = stack.popleft()
            for v in graph[current]:
                if paths[current] * graph[current][v] > paths[v]:
                    stack.append(v)
                    paths[v] = max(paths[current] * graph[current][v], paths[v])
        return paths[end] 


import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], probs: List[float], s: int, t: int) -> float:
        # first build the graph
        graph = {u: {} for u in range(n)}
        for (u, v), prob in zip(edges, probs):
            graph[u][v] = prob
            graph[v][u] = prob

        # run A* search
        frontier = [(-1, s)]
        seen = set()

        while len(frontier) != 0:
            neg_path_prob, u = heapq.heappop(frontier)
            if u == t:
                return -neg_path_prob

            seen.add(u)
            for v, edge_prob in graph[u].items():
                if v not in seen:
                    heapq.heappush(frontier, (neg_path_prob * edge_prob, v))
        return 0

import heapq 
from math import log2

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        AdjList = [set() for _ in range(n)]
        for (u, v), prob in zip(edges, succProb):
            AdjList[u].add(( -log2(prob), v ))
            AdjList[v].add(( -log2(prob), u ))
        dist = [float('inf')]*n
        dist[start] = 0
        heap = [(0, start)]
        explored = set()
        while heap:
            d, curr = heapq.heappop(heap)
            explored.add(curr)
            for (val, node) in AdjList[curr]:
                if node not in explored:
                    if dist[curr] + val < dist[node]:
                        dist[node] = dist[curr] + val
                        heapq.heappush(heap, (dist[node], node))
        return 2 ** (-dist[end])

from collections import deque

class Solution:
    def maxProbability(self, n: int, edges, succProb, start: int, end: int) -> float:

        m = [{} for i in range(n)]
        for edge, d in zip(edges, succProb):
            s, e = edge
            m[s][e] = m[e][s] = d

        res = [0] * n
        res[start] = 1
        q = [[-1, start]]

        while q and res[end] == 0:
            tmp = heapq.heappop(q)
            prob, cur = -tmp[0], tmp[1]
            res[cur] = prob
            for nxt, np in m[cur].items():
                if res[nxt] != 0: continue
                heapq.heappush(q, [-np * prob, nxt])
        return res[end]

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = collections.defaultdict(list)
        for (s, e), prob in zip(edges, succProb):
            graph[s].append((e, prob))
            graph[e].append((s, prob))
        
        visited = [0] * n
        
        prio = [(-1, start)]
        while prio:
            prob, vertex = heapq.heappop(prio)
            
            if prob > visited[vertex]:
                continue
            visited[vertex] = prob
            
            if vertex == end:
                return -prob
            
            for neighbor, cost in graph[vertex]:
                if prob * cost < visited[neighbor]:
                    visited[neighbor] = prob * cost
                    heapq.heappush(prio, (prob * cost, neighbor))
        
        return 0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        g = defaultdict(list)
        
        '''
        {0: [(0.5, 1), (0.2, 2)], 1: [(0.5, 0), (0.5, 2)], 2: [(0.5, 1), (0.2, 0)]}
        '''
        for edge, prob in zip(edges, succProb):
            x, y = edge
            g[x].append((prob, y))
            g[y].append((prob, x))
            
        print(g)
        
        q, vis = [(-1, start)], set()
        cand = []
        while q:
            prob, node = heapq.heappop(q)
            
            # print((prob, node))
            if node == end:
                cand.append(-prob)
            
            if node not in vis:
                vis.add(node)
                
                for next_prob, nbrs in g[node]:
                    if nbrs not in vis:
                        heapq.heappush(q, (prob * next_prob, nbrs))
                        
                        
        print(cand)
        return max(cand, default=0)
            
            


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        # undirected graph
        # weighted positive edges
        # single start
        
        # shortest path <-> longest path
        
        # 最短路 正边权 稀疏图 -》 stack dijkstra

        N = 100010
        dist = [2 for i in range(N)] 
        seen = set()
        
        h = [-1 for i in range(N)]
        e = {}
        ne = {}
        w = {}
        idx = 0
        
        # build singly linked list graph
        def add(a, b, c, idx):
            e[idx], w[idx] = b, c
            ne[idx] = h[a] 
            h[a] = idx
            
        for edge, prob in zip(edges, succProb):
            add(edge[0], edge[1], prob, idx)
            idx += 1
            add(edge[1], edge[0], prob, idx)
            idx += 1
        
        
        def heap_dijkstra():
            dist[start] = 1
            heap = []
            heapq.heappush(heap, (-1, start))

            while heap:
                t = heapq.heappop(heap)
                vertex, distance = t[1], -t[0]
                if vertex in seen:
                    continue
                    
                seen.add(vertex)
                    
                i = h[vertex] # idx
                while i != -1:
                    j = e[i]
                    if dist[j] == 2 or dist[j] < distance * w[i]:
                        dist[j] = distance * w[i]
                        heapq.heappush(heap, (-dist[j], j))

                    i = ne[i]
            return dist[end]
        
        '''
        graph = [[1e-6 for i in range(N)] for j in range(N)]

        for edge, prob in zip(edges, succProb):
            graph[edge[0]][edge[1]] = max(prob, graph[edge[0]][edge[1]])   
            graph[edge[1]][edge[0]] = max(prob, graph[edge[1]][edge[0]])            
        
        def dijkstra():
            dist[start] = 1
            
            for i in range(n):
                t = -1
                for j in range(n):
                    if not seen[j] and (t == -1 or dist[t] < dist[j]):
                        t = j
                
                seen[t] = True
                for j in range(n):
                    dist[j] = max(dist[j], dist[t] * graph[t][j])
            
            return dist[end]
        
        '''
        

        
        output = heap_dijkstra()

        if output == 2 or output < 1e-5:
            return 0.0
        else:
            return output

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dp = [0.0 for _ in range(start)] + [1.0] + [0.0 for _ in range(start+1,n)]
        # dp[i] is the prob of getting node i from node start
        
        graph = defaultdict(list)
        for (u,v),p in zip(edges,succProb):
            graph[u].append((v,p))
            graph[v].append((u,p))
        
        # dijkstra's algorithm
        heap = [(-1.0, start)]
        
        while heap:
            p, cur = heapq.heappop(heap)
            if cur==end:
                return -p
            for child, prob in graph[cur]:
                if dp[cur]*prob>dp[child]:
                    dp[child] = dp[cur]*prob
                    heapq.heappush(heap, (-dp[child],child))
        return 0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        dist = [-math.inf for _ in range(n)]
        dist[start] = 1
        max_heap = [(1, start)]
        graph = collections.defaultdict(list)
        
        for (u, v), w in zip(edges, succProb):
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        while max_heap:
            prob, node = heapq.heappop(max_heap)
            prob = abs(prob) # make it positive to avoid confusion
            if node == end:
                return prob
            for adj, next_prob in graph[node]:
        # if we are coming from the start node, make sure we don't multiply it by 0
                next_prob *= prob
                if dist[adj] < next_prob:
                    dist[adj] = next_prob
                    heapq.heappush(max_heap, (-next_prob, adj))
        return 0.0


from collections import deque
from heapq import heappush, heappop

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = [[] for _ in range(n)]
        for (u, v), wt in zip(edges, succProb):
            graph[u].append((v, wt))
            graph[v].append((u, wt))
        
        probabilities = [0 for _ in range(n)]
        probabilities[start] = 1
        h = [(-probabilities[start], start)]
        visited = set()
        while h:
            curr_prob, curr_node = heappop(h)
            curr_prob *= -1
            visited.add(curr_node)
            for v, wt in graph[curr_node]:
                if v not in visited:
                    if probabilities[curr_node] * wt > probabilities[v]:
                        probabilities[v] = probabilities[curr_node] * wt
                        heappush(h, (-probabilities[v], v))
        return probabilities[end]
            
        
        


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dist = [0.0]*n
        dist[start] = 1.0

        for i in range(n):
            flag = False
            for (a,b), p in zip(edges, succProb):
                if dist[a]==0.0 and dist[b]==0.0:continue
                Max = max(dist[a], dist[b])*p
                if Max > dist[a]:
                    dist[a] = Max
                    flag = True
                if Max > dist[b]:
                    dist[b] = Max
                    flag = True
            if not flag:
                break
                
        return dist[end]

from collections import defaultdict
from heapq import heappush, heappop
from typing import List


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        adjlist = defaultdict(list)
        for edge, succ in zip(edges, succProb):
            adjlist[edge[0]].append([edge[1], succ])
            adjlist[edge[1]].append([edge[0], succ])
        cost = [float('-inf')] * n
        hp = [(-1, start)]
        visited = set()
        while hp:
            price, node = heappop(hp)
            price = -price
            if node in visited:
                continue
            for neigh, neighcost in adjlist[node]:
                heappush(hp, (-(price * neighcost), neigh))
            cost[node] = price
            visited.add(node)
        print(cost)
        if cost[end] == float('-inf'):
            return 0
        return cost[end]


from heapq import *
from collections import defaultdict

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        # construct graph
        graph = defaultdict(list)
        
        for edge, prob in zip(edges, succProb):
            src, dst = edge
            graph[src].append((dst, prob))
            graph[dst].append((src, prob))
        
        # Dijkstra (-ve probabilities for max heap)
        max_heap = [(-1.0, start, None)]
        
        while max_heap:
            probability, node, parent = heappop(max_heap)
            probability = -probability
            # print(f\"Node: {node}\")
            
            if node == end:
                return probability
            
            neighbors = graph[node]
            
            for neighbor, weight in neighbors:
                # don't go back to the parent
                if neighbor != parent:
                    heappush(max_heap, (-weight*probability, neighbor, node))
        
        return 0
        


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        g = collections.defaultdict(list)
        for (u, v), p in zip(edges, succProb):
            g[u].append((v, p))
            g[v].append((u, p))
      #  print(g)
        q = [(-1, start)]
        seen = set()
        while q:
         #   print(q)
            p, u = heapq.heappop(q)
            if u in seen:
                continue
            seen.add(u)
            if u == end:
                return -p
            for v, pp in g[u]:
               # print(v, pp, seen)
                if v not in seen:
                    heapq.heappush(q, (p * pp, v))
                    #seen.add(v)
        return 0


from collections import defaultdict
from heapq import heappop, heappush
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        adjlist = defaultdict(list)
        for pair, prob in zip(edges, succProb):
            p, c = pair
            adjlist[p].append([c, prob])
            adjlist[c].append([p, prob])
        probability = {i: float('-inf') for i in range(n)}
        hq = [[-1, start]]
        visited = set()
        while hq:
            cost, curr = heappop(hq)
            cost = -cost
            if curr in visited:
                continue
            for child, price in adjlist[curr]:
                heappush(hq, [-(price*cost), child])
            visited.add(curr)
            if probability[curr] < cost:
                probability[curr] = cost
        if probability[end] == float('-inf'):
            return 0
        return probability[end]


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        G = defaultdict(list)
        P = {}
        for (i, j), p in zip(edges, succProb):
            G[i].append(j)
            G[j].append(i)
            P[i, j] = P[j, i] = p
        hp = [(-1, start)]
        seen = {start: 1}
        while hp:
            prob, node = heapq.heappop(hp)
            prob *= -1
            if node == end:
                return prob
            for nei in G[node]:
                tmp = seen[node] * P[node, nei]
                if nei not in seen or seen[nei] < tmp:
                    heapq.heappush(hp, (-tmp, nei))
                    seen[nei] = tmp
        return 0
                    


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dp = [0.0 for _ in range(start)] + [1.0] + [0.0 for _ in range(n)]
        graph = defaultdict(list) # undirected
        for (u,v),p in zip(edges,succProb):
            graph[u].append((v,p))
            graph[v].append((u,p))
        
        queue = [(-1.0,start)] # tuple[0] is current point, tuple[1] is prob of getting cur from start

        while queue:
            for _ in range(len(queue)):
                p, cur = heapq.heappop(queue)
                if cur==end:
                    return -p
                for child,prob in graph[cur]:
                    if dp[cur]*prob > dp[child]:
                        dp[child] = dp[cur]*prob
                        heapq.heappush(queue,(-dp[child], child))
                            
                        
        return 0

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        dist = [-math.inf for _ in range(n)]
        dist[start] = 1
        max_heap = [(1, start)]
        # graph = collections.defaultdict(list)
        graph = collections.defaultdict(dict)
        
        for (u, v), w in zip(edges, succProb):
            # graph[u].append((v, w))
            # graph[v].append((u, w))
            graph[u][v] = w
            graph[v][u] = w
            
        while max_heap:
            prob, node = heapq.heappop(max_heap)
            prob = abs(prob) # make it positive to avoid confusion
            if node == end:
                return prob
            for adj in graph[node]:
        # if we are coming from the start node, make sure we don't multiply it by 0
                next_prob = graph[node][adj]
                next_prob *= prob
                if dist[adj] < next_prob:
                    dist[adj] = next_prob
                    heapq.heappush(max_heap, (-next_prob, adj))
        return 0.0