<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>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

int speed = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct edge {
    int a;
    int b;
    double p;
    edge* next = nullptr;

    edge(int _a, int _b, double _p): a(_a), b(_b), p(_p) {};
};

class Solution {
public:
    // Utilize Dijkstra's algorithm
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        // Base case
        if(start_node == end_node)
            return 1.0;

        // Transform set of edges into LL for fast deletes
        edge* dummy = new edge(-1, -1, 0.0);
        edge* prev = dummy;
        for(int i = 0; i < edges.size(); i++) {
            edge* temp = new edge(edges[i][0], edges[i][1], succProb[i]);
            prev->next = temp;
            prev = temp;
        }
        edge* eHead = dummy->next;

        // Hold list of nodes and their current chance
        // for easy sorting
        priority_queue<pair<double, int>> toVisit;
        toVisit.push({1.0, start_node});

        // List of best chances to reach each node
        vector<double> maxChance(n, 0.0);
        maxChance[start_node] = 1.0;

        // While there are nodes to visit
        while(!toVisit.empty()) {
            // Pop off node with highest chance
            auto node_pair = toVisit.top();
            int a = node_pair.second;
            double p = node_pair.first;
            toVisit.pop();
//            cout << "p(" << a << ") = " << p << endl;

            // If we've already found a higher chance
            // path for this node (p isn't current!)
            if(maxChance[a] > p)
                continue;

            // Find paths involving a
            edge* cur = eHead;
            prev = dummy;
            while(cur != nullptr) {
//                cout << "Checking edge [" << cur->a << ", " << cur->b << "] " << cur->p << endl;

                // Does this edge have node a?
                if(cur->a == a || cur->b == a) {
//                    cout << "Edge has " << a << endl;
                    // Node this edge goes to
                    int b;
                    if(cur->a == a)
                        b = cur->b;
                    else
                        b = cur->a;

                    // Does this path to b have a new higher chance?
                    if(p * cur->p > maxChance[b]) {
                        // Update b's max probability
                        maxChance[b] = p * cur->p;

                        // Add b as a node to visit
                        toVisit.push({ maxChance[b], b });
                    }

                    // Delete this edge
                    if(cur == eHead)
                        eHead = cur->next;
                    prev->next = cur->next;
                    delete cur;
                    cur = prev->next;

//                    cout << "Deleted edge. [" << prev->a << ", " << prev->b << "] -> ";
//                    if(cur == nullptr)
//                        cout << "NULL\n";
//                    else
//                        cout << "[" << cur->a << ", " << cur->b << "]\n";
                } else {
                    prev = cur;
                    cur = cur->next;
                }
            }
        }

        return maxChance[end_node];
    }
};
60996