[C++] 99%, Dijkstra/Prim algo
IntuitionReverse the edges of the graph. This simplifies the reachability problem. Then we run dijkstra algo, but a variant where we try to minimize the the wei
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Reverse the edges of the graph. This simplifies the reachability problem. Then we run dijkstra algo, but a variant where we try to minimize the the weight of an edge chosen to reach some node n. On top of that, we have the constraint that in_degree (because graph is reversed) should be <= threshold.

But the threshold doesn't matter as in the end we will have a tree where in_degree is always 1.

To put it more simply, at any point, say we know the solution for some subset of nodes (reachable from node 0 and minimized weights). Then out of all the possible outgoing edges from this set, we choose the one with:
- Min edge weight

But what if there's another smaller edge to one of our subset of the nodes from outside the set? Doesn't matter as all the edges going outside our set are >= the maxm edge weight found so far. So we are bounded. Similar logic as Dijktra for correctness
# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(V + ElogV)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    // Custom Dijkstra?

    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
       
        vector<vector<pair<int, int>>> g(n);
        for (auto& e: edges) {
            g[e[1]].push_back({e[0], e[2]});
        }    

        struct Node {
            int v, w;
            bool operator<(const Node& other) const {
                return w > other.w;
            }
        };

        priority_queue<Node> pq;

        pq.push({0, 0});
    
        int ans = 0;
        int visited_nodes = 0;

        vector<bool> vis(n);
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            
            int u = top.v, w = top.w;
         
            if (vis[u]) continue;
            visited_nodes++;
            ans = max(ans, w);
           
            // cout << from << " " << u << " " << w << "\n";
            vis[u] = true;
          
            for (auto& e: g[u]) {
                int v = e.first;
                if (!vis[v]) {
                    pq.push({v, e.second});
                }
              
            }
        }
        if (visited_nodes != n) return -1;
     
        return ans;
    }
};
```
['C++']