C++刷LeetCode（5211. 概率最大的路径）【图】【广度优先搜索】
题目描述：给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges = 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。
示例 1：
输入：n = 3, edges = [,,], succProb = , start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
示例 2：
输入：n = 3, edges = [,,], succProb = , start = 0, end = 2
输出：0.30000
示例 3：
输入：n = 3, edges = [], succProb = , start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径
提示：
2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb <= 1
每两个节点之间最多有一条边
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
//广度优先搜索
//构建邻接矩阵
vector<vector<pair<int, double> > > graph(n);
for(int i = 0; i < edges.size(); i++) {
graph].push_back({edges, succProb});
graph].push_back({edges, succProb});
}
vector<double> prob_max(n);//这个向量构建是关键！！！
queue<pair<int, double>> store;
store.push({start, 1.0});
prob_max = 1.0;
while(!store.empty()) {
pair<int, double> temp1 = store.front();
store.pop();
for(auto& cha : graph) {
double temp2 = temp1.second * cha.second;
if(cha.first == end) {
prob_max = max(temp2, prob_max);
continue;
}
if(prob_max < temp2) {
prob_max = temp2;
store.push({cha.first, temp2});
}
}
}
return prob_max;
}
}; {:10_275:}
页:
[1]