Leetcode daily 2

Today's problem is standard problem of BFS,
But it can teach us some c++ concepts such as using priority_queue correctly.

For this specific solution i have made a custom element and overwritten the less-than operator for it.
this makes me go thru the graph in order of probablity.

higher probability region will be explored first.
and this solution is accepted.

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<int,double>>> adj(n);
        int cnt = 0;
        for(auto i : edges) {

            adj[i[0]].push_back({i[1], succProb[cnt]});
            adj[i[1]].push_back({i[0], succProb[cnt]});
            cnt++;
        } 
        struct  elem { 
            double prob;
            int point;
            bool operator < (const struct elem &a) const { 
                return this->prob < a.prob;
            }
        };
        /* will pick up higher probabilities first */

        vector<double> probs(n,0.);
        probs[start] = 1.;

        priority_queue<elem> pq;
        pq.push(elem{1., start});
        while(!pq.empty()) {
            elem t = pq.top();
            pq.pop();
            cout << t.point << endl; 
            if (t.point == end) { 
                break; 
            }
            for(auto i : adj[t.point])  { 
                // probs[i.first] = max(probs[i.first],
                //     probs[t.point] * i.second);
                // pq.push(elem{probs[i.first],i.first}); // we just push the point, and we dont care about the prob.
                if (probs[i.first] < probs[t.point] * i.second) { 
                    probs[i.first]  = probs[t.point] * i.second;
                    pq.push(elem{probs[i.first], i.first});
                }
            }
        }
        return probs[end];
    }
};

But seems like there are more complicated and FAST solutions for this problem.

For example using this Graph-DP.

which has half the runtime.

Blog

pastaPicaso

Join Our Newsletter. No Spam, Only the good stuff.

Related