1514.概率最大的路径

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

一、Dijkstra变种

原算法求最短路径，此处改为求最大概率（边）

import heapq
#py没有大根堆。存入负权值，用小根堆实现大根堆
class BigHeap:
    def __init__(self):
        self.arr = list()
    def insert(self, nodeState):
        weight = nodeState[0]
        node = nodeState[1]
        heapq.heappush(self.arr, (-weight, node))   # 存入负权值
    def heapify(self):
        heapq.heapify(self.arr)
    def pop(self):
        weight, node = heapq.heappop(self.arr)
        # 先取出再转负
        return (-weight, node)
    def get_top(self):
        if not self.arr:
            return
        return -self.arr[0]
    def isEmpty(self):
        return not self.arr

class Solution:
    def maxProbability(self, n: int, edges, succProb, start: int, end: int) -> float:
        graph = {}
        for i in range(n):
            graph[i] = list()
        for i in range(len(edges)):
            f = edges[i][0]
            t = edges[i][1]
            w = succProb[i]
            # 双向图
            graph[f].append((t, w))
            graph[t].append((f, w))

        probTo = [-1] * n
        probTo[start] = 1
        # 最大堆，（从起点到当前节点）概率最大的节点优先弹出
        heap = BigHeap()
        heap.insert((1, start))	#起点到自己的概率为1

        while not heap.isEmpty():
            curProb, curNode = heap.pop()
            if curNode == end:
                return curProb
            if curProb < probTo[curNode]:
                continue
            for neighbor in graph[curNode]:
                nextNode = neighbor[0]
                nextWeight = neighbor[1]
                # 计算到下个结点的概率
                nextPorb = curProb * nextWeight
                # 如果比记录的还大，更新记录，并将该节点入堆
                if nextPorb > probTo[nextNode]:
                    probTo[nextNode] = nextPorb
                    heap.insert((nextPorb, nextNode))

        return 0