Re: [閒聊] 每日leetcode
1514. Path with Maximum Probability
## 思路
Dijkstra找路徑, 求最大機率所以用max_heap
## Code
```python
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb:
List[float], start_node: int, end_node: int) -> float:
graph = defaultdict(list)
for (a, b), prob in zip(edges, succProb):
graph[a].append((prob, b))
graph[b].append((prob, a))
dist = [0.0] * n
dist[start_node] = 1.0
max_heap = [(-1.0, start_node)]
while max_heap:
curr_prob, node = heapq.heappop(max_heap)
if node == end_node:
return -curr_prob
for prob, neighbor in graph[node]:
if dist[neighbor] >= -curr_prob * prob:
continue
dist[neighbor] = -curr_prob * prob
heapq.heappush(max_heap, (-dist[neighbor], neighbor))
return 0
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.46 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724769654.A.B32.html
討論串 (同標題文章)
完整討論串 (本文為第 771 之 1550 篇)：