LeetCode 1514 Path with Maximum Probability

标签: 图算法 LeetCode 发布于:2022-02-10 00:13:05 编辑于:2022-02-10 01:07:50 浏览量:326

概述

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];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/