Longest Path Solution

Leetcode #1514
 avatar
unknown
c_cpp
a month ago
1.3 kB
4
Indexable
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int src, int dst) {
        unordered_map<int, vector<pair<double, int>>> graph;
        
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            double dist = succProb[i];
            
            if (!graph.count(u)) {
                graph[u] = {};
            }
            if (!graph.count(v)) {
                graph[v] = {};
            }
            
            graph[u].push_back({dist, v});
            graph[v].push_back({dist, u});
        }
        
        priority_queue<pair<double, int>> pq;
        
        pq.push({1, src});
        
        bool finalAns = 0;
        
        vector<double> distances(n, 0);
        
        while (!pq.empty()) {
            auto [currProb, currNode] = pq.top();
            pq.pop();
            
            for (auto [weight, child]: graph[currNode]) {
                double newDist = currProb * weight;
                
                if (newDist > distances[child]) {
                    pq.push({newDist, child});
                    distances[child] = newDist;
                }
                
            }
        }
        
        return distances[dst];
    }
};
Editor is loading...
Leave a Comment