<p>You are given an undirected weighted graph of&nbsp;<code>n</code>&nbsp;nodes (0-indexed), represented by an edge list where&nbsp;<code>edges[i] = [a, b]</code>&nbsp;is an undirected edge connecting the nodes&nbsp;<code>a</code>&nbsp;and&nbsp;<code>b</code>&nbsp;with a probability of success of traversing that edge&nbsp;<code>succProb[i]</code>.</p>

<p>Given two nodes&nbsp;<code>start</code>&nbsp;and&nbsp;<code>end</code>, find the path with the maximum probability of success to go from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>&nbsp;and return its success probability.</p>

<p>If there is no path from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>, <strong>return&nbsp;0</strong>. Your answer will be accepted if it differs from the correct answer by at most <strong>1e-5</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png" style="width: 187px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
<strong>Output:</strong> 0.25000
<strong>Explanation:</strong>&nbsp;There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png" style="width: 189px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
<strong>Output:</strong> 0.30000
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png" style="width: 215px; height: 191px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
<strong>Output:</strong> 0.00000
<strong>Explanation:</strong>&nbsp;There is no path between 0 and 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10^4</code></li>
	<li><code>0 &lt;= start, end &lt; n</code></li>
	<li><code>start != end</code></li>
	<li><code>0 &lt;= a, b &lt; n</code></li>
	<li><code>a != b</code></li>
	<li><code>0 &lt;= succProb.length == edges.length &lt;= 2*10^4</code></li>
	<li><code>0 &lt;= succProb[i] &lt;= 1</code></li>
	<li>There is at most one edge between every two nodes.</li>
</ul>

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        // modified Djikstra's algoritm, using multiplication rather than addition

        // FIXME: barely accepted with set not priority_queue, borderline TLE after 19/20

        // set initial conditions: identity for start node, worst possible for others
        vector<double> prob(n);
        prob[start_node] = 1.0;
/*
        // FIXME: TLE; use priority queue?
        set<int> unvisited;
        for (int i=0; i<n; ++i) {
            pair<double, int> p = { prob[i], i };
            unvisited.insert(i);
        }
*/
/* actually pair priority queue is worse... TLE after 12/20
        priority_queue<pair<double, int>> unvisited; 
        for (int i=0; i<n; ++i) {
            pair<double, int> p = { prob[i], i };
            unvisited.push(p);
        }
*/        
        // try again with better implementation
        priority_queue<pair<double, int>> unvisited; 
        unvisited.push({1.0, start_node});
        set<int> visited;

        while (!unvisited.empty()) {
/* try again with better implementation
            // pick the nearest i.e. with highest probability
            auto it = unvisited.begin();
            int current = *it;
            while (it != unvisited.end()) {
                if (prob[current] < prob[*it]) {
                    current = *it;
                }
                ++it;
            }

            // remove from unvisited
            unvisited.erase(current);
*/
/* actually pair priority queue is worse... TLE after 12/20
   try again with better implementation */
            int current = unvisited.top().second;
            unvisited.pop();

            if (visited.contains(current)) {
                continue;
            }
            visited.insert(current);

            // early-out improves from TLE 15/20 to TLE 19/20
            if (current == end_node) {
                break;
            }

            bool changed = false;

            // for each outbound edge from current, update probabilities
            for (int e=0; e<edges.size(); ++e) {
                if (edges[e][0] == current) {
                    double newprob = prob[current] * succProb[e];
                    if (prob[edges[e][1]] < newprob) {
                        prob[edges[e][1]] = newprob;
/* actually pair priority queue is worse... TLE after 12/20
                        changed = true;
*/
                        unvisited.push({newprob, edges[e][1]});
                    }
                } else
                if (edges[e][1] == current) {
                    double newprob = prob[current] * succProb[e];
                    if (prob[edges[e][0]] < newprob) {
                        prob[edges[e][0]] = newprob;
/* actually pair priority queue is worse... TLE after 12/20
                        changed = true;
*/       
                        unvisited.push({newprob, edges[e][0]});
                    }
                }
            }

/* actually pair priority queue is worse... TLE after 12/20
            if (changed) {
                // update priority_queue with new probabilities
                // no particularly efficient way other than removing and re-inserting all

                vector<pair<double, int>> shelf;

                while (!unvisited.empty()) {
                    shelf.push_back(unvisited.top());
                    unvisited.pop();                    
                }

                for (pair<double,int>& item : shelf) {
                    item.first = prob[item.second];
                    unvisited.push(item);
                }
            }
*/            
        }

        return prob[end_node];
    }
};
57518