Leetcode 1325 Solution

This article provides solution to leetcode question 1325 (path-with-maximum-probability)
Categories:
Tags:
Access this page by simply typing in "lcs 1325" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/path-with-maximum-probability

Solution

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = collections.defaultdict(list)
        for (src, dst), prob in zip(edges, succProb):
            graph[src].append((dst, prob))
            graph[dst].append((src, prob))



        q = []
        heapq.heappush(q, (-1, start))
        visited = set()



        while q:
            node_prob, node = heapq.heappop(q)



            if node in visited:
                continue



            if node == end:
                return -node_prob



            visited.add(node)



            for nei_node, prob in graph[node]:
                if nei_node in visited:
                    continue



                heapq.heappush(q, (node_prob * prob, nei_node))



        return 0