乘一堆负号好麻烦
自讨苦吃
但我也懒得去找怎么让heap是maxheap了
对不起
def maxProbability(self, n: int, edges: List[List[int]], succProb:
List[float], start_node: int, end_node: int) -> float:
g = defaultdict(list)
for i in range(len(edges)):
g[edges[i][0]].append((edges[i][1],succProb[i]))
g[edges[i][1]].append((edges[i][0],succProb[i]))
# dijkstra
probes = [0.0 for _ in range(n)]
probes[start_node] = 1.0
pq = [(-1.0, start_node)]
while pq:
cur_prob, cur_node = heappop(pq)
if -1.0*cur_prob < probes[cur_node]:
continue
if cur_node == end_node:
return -1.0*cur_prob
for n, p in g[cur_node]:
if cur_prob*p < -1.0*probes[n]:
probes[n] = -1.0*cur_prob*p
heappush(pq, (cur_prob*p, n))
return 0.0