<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){
        double prob[10000]={0};
        prob[start_node]=1;
        int e=edges.size();
        for (int i = 1; i <= n-1; i++) {
            bool hasUpdate=false;
            for (int j = 0; j < e; j++) {
                int u = edges[j][0];
                int v = edges[j][1];
                double pathprob = succProb[j];
                if (prob[u]*pathprob > prob[v]){
                    prob[v] = prob[u]*pathprob;
                    hasUpdate = true;
                }
                if (prob[v]*pathprob > prob[u]){
                    prob[u] = prob[v]*pathprob;
                    hasUpdate = true;
                }
            }
            if(!hasUpdate){break;}
            // for(int x=0;x<n;x++)cout<<prob[x]<<" ";
            // cout<<"\n";
        }
        return prob[end_node];
    }
//     void dfs(vector<bool> &visited,int current,vector<vector<double>>& e,double currp, double &maxp,int end_node, int n){
//     visited[current]=true;
//     // cout<<current<<" "<<currp<<"\n";
//     if(current==end_node){
//         maxp = max(maxp,currp);
//         visited[current]=false;
//         return;
//     }
    
//     for(int i=0;i<n;i++){
//         double prob = e[current][i];//*((e + current * n) + i);
//         if(prob){
//           if(!visited[i])dfs(visited,i,e,currp*prob,maxp,end_node,n);  
//         }
//     }
//     visited[current]=false;
// }
// double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
//     vector<vector<double>> e(n,vector<double>(n,0));
//     int ne=edges.size();
//     for (int i=0;i<ne;i++) {
//         e[edges[i][0]][edges[i][1]]=succProb[i];
//         e[edges[i][1]][edges[i][0]]=succProb[i];
//     }
//     vector<bool> visited(n,false);
//     double maxp=0;
//     dfs(visited,start_node,e,1,maxp,end_node,n);
//     return maxp;
// }
    //     void dfs(vector<bool> &visited,int current,vector<vector<pair<int,double>>> &e,double currp, double &maxp,int end_node){
    //     visited[current]=true;
    //     // cout<<current<<" "<<currp<<"\n";
    //     if(current==end_node){
    //         maxp = max(maxp,currp);
    //         visited[current]=false;
    //         return;
    //     }
    //     for(auto& it:e[current]){
    //         int neighbour = it.first;
    //         double pathprob = it.second;
    //         if(!visited[neighbour])dfs(visited,neighbour,e,currp*pathprob,maxp,end_node);
    //     }
    //     visited[current]=false;
    // }
    // double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
    //     vector<vector<pair<int,double>>> e(n);
    //     int ne=edges.size();
    //     for (int i=0;i<ne;i++) {
    //         e[edges[i][0]].push_back(make_pair(edges[i][1],succProb[i]));
    //         e[edges[i][1]].push_back(make_pair(edges[i][0],succProb[i]));
    //     }
    //     vector<bool> visited(n,false);
    //     double maxp=0;
    //     dfs(visited,start_node,e,1,maxp,end_node);
    //     return maxp;
    // }
};
52458