Description

Submission

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<double> dp(n, 0);  // max prob from start to node i
        map<int, vector<pair<int, double>>> nextNodes;

        for(int i = 0; i < edges.size(); ++i) {
            nextNodes[edges[i][0]].push_back({edges[i][1], succProb[i]});
            nextNodes[edges[i][1]].push_back({edges[i][0], succProb[i]});
        }

        queue<int> q;
        dp[start] = 1;
        q.push(start);

        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            for(auto& nextNode: nextNodes[cur]) {
                int next = nextNode.first;
                double nextVal = nextNode.second;
                
                double newProb = nextVal * dp[cur];

                if(newProb > dp[next]) { 
                    dp[next] = newProb;
                    q.push(next);
                }
            }
        }

        return dp[end];
    }
};