LeetCode 1514 Path with Maximum Probability
概述
https://leetcode.com/problems/path-with-maximum-probability/
Dijkstra 算法（O(n^2) 的实现）
佛了，原本 maxVal 不小心写错成 int 类型了，看了半天才看出来问题。
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<double>> graph(n, vector<double>(n, 0));
for (int i = 0; i < edges.size(); i ++) {
graph[edges[i][0]][edges[i][1]] = succProb[i];
graph[edges[i][1]][edges[i][0]] = succProb[i];
}
vector<double> p(n, 0);
vector<bool> fixed(n, false);
p[start] = 1;
int c = start;
while (true) {
fixed[c] = true;
int maxIdx = -1;
double maxVal = 0;
for (int i = 0; i < n; i ++) {
if (!fixed[i]) {
p[i] = max(p[i], p[c] * graph[c][i]);
if (p[i] > maxVal) {
maxVal = p[i];
maxIdx = i;
}
}
}
if (maxIdx == -1) break;
if (maxIdx == end) break;
c = maxIdx;
}
return p[end];
}
};
上面这个 TLE 了。
Dijkstra 算法（O(nlogn) 的实现）
上面的实现的问题在于，明明题目已经给了所有的边，我们却还不得不将其扩充成全连接的图，变成 n^2 个边。
下面的实现基于优先级队列。
实现的过程中还碰见一个坑，下面的代码会导致死循环，因为当 pq 为空时调用 top() 返回的值是未定义的，我们必须在此之前检查其是否为空。
while (fixed[pq.top().second]) {
pq.pop();
}
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<double, int>>> graph(n);
for (int i = 0; i < edges.size(); i ++) {
graph[edges[i][0]].push_back({succProb[i], edges[i][1]});
graph[edges[i][1]].push_back({succProb[i], edges[i][0]});
}
priority_queue<pair<double, int>> pq;
pq.push({1, start});
vector<double> p(n, 0);
vector<bool> fixed(n, false);
p[start] = 1;
while (!pq.empty()) {
auto c = pq.top();
pq.pop();
fixed[c.second] = true;
if (c.second == end) break;
for (auto& e : graph[c.second]) {
if (!fixed[e.second]) {
if (p[e.second] < c.first * e.first) {
p[e.second] = c.first * e.first;
pq.push({p[e.second], e.second}); // only when it's updated we put it back to pq or we will TLE
}
}
}
}
return p[end];
}
};