推 CanIndulgeMe: 別再卷了...... 08/28 00:02
→ Rushia: 只能乘負號 py大便heap 08/28 00:03
乘一堆負號好麻煩
自討苦吃
但我也懶得去找怎麼讓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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724774543.A.C3F.html