Binary Search With BFS Algorithm. Simple And Easy to Understand
IntuitionThe idea is to find a weight at which all the three constraints can be satisfied. Using Linear Search and BFS or Binary Search with BFS works but since
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The idea is to find a weight at which all the three constraints can be satisfied. Using Linear Search and BFS or Binary Search with BFS works but since Binary Search with BFS has better time complexity, below solution is for Binary Search with BFS Algorithm

# Approach
<!-- Describe your approach to solving the problem. -->
1. The Approach here is to identify a minimum weight at which all the nodes can reach to node 0
2. Another thing we need to consider is that there will be N-1 nodes which will reach to node 0
3. Since we are given with a directed graph and we need to reach node 0 from all the n-1 nodes
4. If we will find a path from a node to node 0, we need to use BFS/DFS with complexity O(V+E), which means for all N-1 nodes complexity will become (N)*O(N + E). After that if we use linear search or binary search to find the minimum weight then complexity will increase to (N)\*(N+E)\*min(log Wt, Wt)
5. Instead of Doing above, we can reverse the direction of the edges and instead of finding path from each node to node 0 we will find path from node 0 to all other nodes.
With this Approach we will be doing one bfs that ( N + E) and overall complexity would be ( log Wt)*(N+E)

# Complexity
- Time complexity:O( (Log W)*(N+E) )
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    //This routine creates adjacency matrix of nodes and edges which has weight less than or qual to maximumWeight
    //This Adjacency Marix is created with reverse direction from actual given in input
    //It then uses BFS Algoithm to check if all the nodes can be traversed at this weight or not
    bool IsItPossible(int n, vector<vector<int>>& edges, int maximumWeight) {

        vector<vector<int>> graph(n);
        for(int i = 0; i < edges.size(); i++) {
            if( edges[i][2] <= maximumWeight)
                graph[edges[i][1]].push_back(edges[i][0]);
        }

        //BFS Algorithm
        queue<int> q;
        q.push(0);
        vector<bool> visited(n, false);
        int count = 1; //Count = 1 since 0 is always considered

        visited[0] = true;
        while(q.size() != 0) {
            int node = q.front();
            q.pop();

            for(auto& nbr : graph[node]) {
                if(visited[nbr] == false ) {
                    q.push(nbr);
                    visited[nbr] = true;
                    count++;
                }
            }
        }

        return count == n; //Checks if the count is equal to all the n nodes

    }
    

    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {

        //Calculate the Min and Max weight from the given graph
        int minWt = INT_MAX, maxWt = INT_MIN;
        for(int i = 0; i < edges.size(); i++) {
            minWt = min(minWt, edges[i][2]);
            maxWt = max(maxWt, edges[i][2]);
        }

        //We can use either linear search or binary search to identify the minimum weight
        //If we will go with linear search it will increase the complexity
        //Let's try Binary Search Approach with search space as Min and Max Weight
        //This Algo is similar to Painter's Problem in Binary Search
        int left = minWt, right = maxWt, ans = -1;
        while( left <= right ) {
            int mid = ( left + right ) / 2;

            bool res = IsItPossible(n, edges, mid);
            if( res ) { 
                ans = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return ans;
    }
};
```
['Binary Search', 'Breadth-First Search', 'Graph', 'C++']