C++刷LeetCode（5211. 概率最大的路径）【图】【广度优先搜索】

糖逗

题目描述：

1. 给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
   
2. 
   
3. 指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
   
4. 
   
5. 如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。
   
6. 
   
7. 
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
    
14. 输出：0.25000
    
15. 解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
    
16. 示例 2：
    
17. 
    
18. 
    
19. 
    
20. 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
    
21. 输出：0.30000
    
22. 示例 3：
    
23. 
    
24. 
    
25. 
    
26. 输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
    
27. 输出：0.00000
    
28. 解释：节点 0 和 节点 2 之间不存在路径
    
29. 
    
30. 
    
31. 提示：
    
32. 
    
33. 2 <= n <= 10^4
    
34. 0 <= start, end < n
    
35. start != end
    
36. 0 <= a, b < n
    
37. a != b
    
38. 0 <= succProb.length == edges.length <= 2*10^4
    
39. 0 <= succProb[i] <= 1
    
40. 每两个节点之间最多有一条边

复制代码

1. class Solution {
   
2. public:
   
3.     double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
   
4.         //广度优先搜索
   
5.         //构建邻接矩阵
   
6.         vector<vector<pair<int, double> > > graph(n);
   
7.         for(int i = 0; i < edges.size(); i++) {
   
8.             graph[edges[i][1]].push_back({edges[i][0], succProb[i]});
   
9.             graph[edges[i][0]].push_back({edges[i][1], succProb[i]});
   
10.         }
    
11.         vector<double> prob_max(n);//这个向量构建是关键！！！
    
12.         queue<pair<int, double>> store;
    
13.         store.push({start, 1.0});
    
14.         prob_max[start] = 1.0;
    
15.         while(!store.empty()) {
    
16.             pair<int, double> temp1 = store.front();
    
17.             store.pop();
    
18.             for(auto& cha : graph[temp1.first]) {
    
19.                 double temp2 = temp1.second * cha.second;
    
20.                 if(cha.first == end) {
    
21.                     prob_max[end] = max(temp2, prob_max[end]);
    
22.                     continue;
    
23.                 }
    
24.                 if(prob_max[cha.first] < temp2) {
    
25.                     prob_max[cha.first] = temp2;
    
26.                     store.push({cha.first, temp2});
    
27.                 }
    
28.             }
    
29.         }
    
30.         return prob_max[end];
    
31.     }
    
32. };

复制代码

小甲鱼的铁粉