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

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

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

&nbsp;
Example 1:



Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation:&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.


Example 2:



Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000


Example 3:



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


&nbsp;
Constraints:


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


class Solution(object):
    def maxProbability(self, n, edges, succProb, start, end):
        adj=[[] for i in range(n)]
        dist=[sys.maxsize for i in range(n)]
        heap=[]
        c=0
        for i,j in edges:
            adj[i].append([j,succProb[c]])
            adj[j].append([i,succProb[c]])
            c+=1
        heapq.heappush(heap,[-1.0,start])
        dist[start]=1
        while(heap):
            prob,u=heapq.heappop(heap)
            for v,w in adj[u]:
                if(dist[v]>-abs(w*prob)):
                    dist[v]=-abs(w*prob)
                    heapq.heappush(heap,[dist[v],v])
        if(sys.maxsize==dist[end]):
            return 0.00000
        else:
            return -dist[end]
class Pair{
    int to;
    double prob;
    public Pair(int to,double prob){
        this.to=to;
        this.prob=prob;
    }
}
class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<Pair>> adj=new ArrayList<>();
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<Pair>());
        }
        for(int i=0;i<edges.length;i++){
            adj.get(edges[i][0]).add(new Pair(edges[i][1],succProb[i]));
            adj.get(edges[i][1]).add(new Pair(edges[i][0],succProb[i]));
        }
        //node,to node,probability
        double probs[]=new double[n];
        Arrays.fill(probs,0.0);
        probs[start]=1.0;
        PriorityQueue<Pair> pq=new PriorityQueue<>((p1,p2)->Double.compare(p2.prob,p1.prob));
        pq.offer(new Pair(start,1.0));
        while(!pq.isEmpty()){
            Pair curr=pq.poll();
            for(Pair x:adj.get(curr.to)){
                if(((curr.prob)*(x.prob))>probs[x.to]){
                    probs[x.to]=((curr.prob)*(x.prob));
                    pq.offer(new Pair(x.to,probs[x.to]));

                }
                else{
                    continue;
                }
            }
        }
        return probs[end];
    }
}
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<int, double>>> graph(n);
        for(int i = 0; i < edges.size(); ++i){
            graph[edges[i][0]].push_back({edges[i][1], succProb[i]});
            graph[edges[i][1]].push_back({edges[i][0], succProb[i]});
        }
        priority_queue<pair<double, int>> pq;
        pq.push({1.0, start});
        vector<bool> visited(n, false);
        vector<double> values(n, 0.0);
        values[start] = 1.0;
        while(!pq.empty()){
            double currValue = pq.top().first, currNode = pq.top().second;
            pq.pop();
            visited[currNode] = true;
            for(int i = 0; i < graph[currNode].size(); ++i){
                double weight = graph[currNode][i].second;
                int nextNode = graph[currNode][i].first;
                if(visited[nextNode] == false){
                    double nextProb = currValue * weight;
                    if(nextProb > values[nextNode])
                        values[nextNode] = nextProb;
                    pq.push({nextProb, nextNode});
                }
            }
        }
        return values[end] == 0.0 ? 0.0 : values[end];
    }
};
var maxProbability = function(n, edges, succProb, start, end) {
    const graph = new Map();
    edges.forEach(([a, b], i) => {
        const aSet = graph.get(a) || [];
        const bSet = graph.get(b) || [];
        aSet.push([b, succProb[i]]), bSet.push([a, succProb[i]]);
        graph.set(a, aSet), graph.set(b, bSet);
    });
    
    const dist = new Array(n).fill(0);
    const vis  = new Array(n).fill(false);
    
    dist[start] = 1;
    
    const getMaxProbNode = () => {
        let maxVal = 0, maxIndex = -1;
        for(let i = 0; i < n; i++) {
            if(maxVal < dist[i] && !vis[i]) {
                maxVal = dist[i], maxIndex = i;
            }
        }
        return maxIndex;
    }
    
    for(let i = 0; i < n - 1; i++) {
        const maxProbNode = getMaxProbNode();
        vis[maxProbNode] = true;
        
        const adjacentNodes = graph.get(maxProbNode) || [];
        const len = adjacentNodes.length;
        for(let j = 0; j < len; j++) {
            const [node, prob] = adjacentNodes[j];
            if(!vis[node] && dist[node] < dist[maxProbNode] * prob) {
                dist[node] = dist[maxProbNode] * prob;
            }
        }
    }
    
    return dist[end];
};
Path with Maximum Probability