<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 {
    // Maintains max heap of size k; sifts element at index idx down
    // time = O(log n)
    // cmp(size_t a, size_t b) -> bool
    //    return true if element at index a is less than element at index b
    //    use greater-than comparator for min-heap
    // swapit(size_t a, size_t b) -> void
    //    called to swap elements at indexes a and b
    template <typename Size, typename Comp, typename Swap>
    static void siftDown(Size k, Size idx, Comp cmp, Swap swapit) {
        if (!k)
            return;
        while (idx < (k - 1)/2) {
            auto idx_left = 2*idx + 1;
            // assert(idx_left < k);
            auto idx_right = idx_left + 1;
            // assert(idx_right < k);
            if (!cmp(idx_right, idx_left))
                idx_left = idx_right;
            if (!cmp(idx, idx_left))
                return;
            swapit(idx, idx_left);
            idx = idx_left;
        }
        if (idx < k/2) {
            auto idx_left = 2*idx + 1;
            // assert(idx_left + 1 >= k);
            if (!cmp(idx, idx_left))
                return;
            swapit(idx, idx_left);
        }
    }
    // Maintains max heap; sifts element at index idx up
    // time = O(log n)
    template <typename Size, typename Comp, typename Swap>
    static void siftUp(Size idx, Comp cmp, Swap swapit) {
        while(idx > 0) {
            auto root = (idx - 1)/2;
            if (!cmp(root, idx))
                break;
            swapit(idx, root);
            idx = root;
        }
    }
    // Makes max heap of size k
    // time = O(n)
    template <typename Size, typename Comp, typename Swap>
    static void makeHeap(Size k, Comp cmp, Swap swap) {
        for (auto idx = k/2; idx--; ) {
            siftDown(k, idx, cmp, swap);
        }
    }
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        //priority_queue<pair<double,unsigned>> q;
        vector<double> maxprob(n, -DBL_MAX);
        vector<unsigned> heap2idx;
        vector<unsigned> idx2heap (n, n); // n marks not-in-heap
        // (heap cannot grow to more than n items)
        auto cmplt = [&maxprob, &heap2idx](const auto a, const auto b) {
            return maxprob[heap2idx[a]] < maxprob[heap2idx[b]];
            // this is max-heap, so return less-than
        };
        auto swapit = [&heap2idx, &idx2heap](const auto a, const auto b) {
            swap(heap2idx[a], heap2idx[b]);
            swap(idx2heap[heap2idx[a]], idx2heap[heap2idx[b]]);
            // < adjust back-indexes after swapping heap items
        };
        heap2idx.reserve(n);
        heap2idx.emplace_back(start);
        maxprob[start] = 0;
        idx2heap[start] = 0;
        vector<unsigned> epos(n + 1);
        vector<pair<double,unsigned>> adj(edges.size()*2);
        for (const auto &edge: edges) {
            ++epos[edge[0]];
            ++epos[edge[1]];
        }
        for (unsigned i = 1, pos = epos[0]; i <= n; ++i)
            epos[i] = pos += epos[i];
        assert(epos[n] == adj.size());
        for (unsigned i = 0; i < edges.size(); ++i) {
            auto prob = log(succProb[i]);
            adj[--epos[edges[i][0]]] = make_pair(prob, (unsigned)edges[i][1]);
            adj[--epos[edges[i][1]]] = make_pair(prob, (unsigned)edges[i][0]);
        }
        while(!heap2idx.empty()) {
            auto u = heap2idx.front();
            if (u == end)
                return exp(maxprob[u]);
            // pop key from heap ...
            heap2idx.front() = heap2idx.back(); // move last key to head
            idx2heap[heap2idx.front()] = 0; // fix index in heap
            idx2heap[u] = n; // mark popped as not-in-heap
            heap2idx.pop_back();
            siftDown(static_cast<unsigned>(heap2idx.size()), static_cast<unsigned>(0), cmplt, swapit); // adjust moved item
            // ... finished
            auto prob = maxprob[u];
            for (auto j = epos[u], l = epos[u + 1]; j < l; ++j) {
                const auto [vprob, v] = adj[j];
                auto nprob = prob + vprob;
                if (nprob <= maxprob[v])
                    continue;
                if (idx2heap[v] == n) { // not in queue, add
                    idx2heap[v] = heap2idx.size();
                    heap2idx.push_back(v);
                } // otherwise, it was in queue and higher, just adjust
                maxprob[v] = nprob;
                siftUp(idx2heap[v], cmplt, swapit);
            }
        }
        return 0.0;
    }
};
58150