1
# Runtime: 755 ms (Top 91.19%) | Memory: 25.4 MB (Top 98.78%)
2
class Solution(object):
3
    def maxProbability(self, n, edges, succProb, start, end):
4
        adj = [[] for i in range(n)]
5
        dist = [sys.maxsize for i in range(n)]
6
        heap = []
7
        c = 0
8
        for i, j in edges:
9
            adj[i].append([j, succProb[c]])
10
            adj[j].append([i, succProb[c]])
11
            c += 1
12
        heapq.heappush(heap, [-1.0, start])
13
        dist[start] = 1
14
        while heap:
15
            prob, u = heapq.heappop(heap)
16
            for v, w in adj[u]:
17
                if dist[v] > -abs(w * prob):
18
                    dist[v] = -abs(w * prob)
19
                    heapq.heappush(heap, [dist[v], v])
20
        if sys.maxsize == dist[end]:
21
            return 0.00000
22
        else:
23
            return -dist[end]