Modified Dijkstra
IntuitionThe problem requires finding the minimum maximum edge weight for a path connecting all nodes. Instead of summing edge weights like standard Dijkstra's

## **Intuition**  
The problem requires finding the **minimum maximum edge weight** for a path connecting all nodes. Instead of summing edge weights like standard Dijkstra's algorithm, we track the **maximum weight encountered along the path** and aim to minimize it.  

---

## **Approach**  
1. **Graph Representation:**  
   - Use an adjacency list (`vector<vector<pair<int,int>>> adj`) to store the **REVERSE** graph, where each node connects to `{neighbor, weight}` pairs.  

2. **Modified Dijkstra’s Algorithm:**  
   - Use a **set (min-heap)** to process nodes with the smallest max-weight encountered so far.  
   - Maintain a **distance array (`dis[]`)** initialized with a large value (`1e9`).  
   - Start with node `0` having weight `0` and process nodes greedily.  

3. **Updating Weights:**  
   - For each neighboring node, update `dis[]` with the **maximum edge weight encountered** along the path.  
   - If a better path is found, update and insert it back into the priority queue.  

4. **Final Calculation:**  
   - The answer is the maximum value in `dis[]`, ensuring all nodes are reachable.  
   - If any node remains unreachable (`1e9`), return `-1`.  

---

## **Complexity Analysis**  
- **Time Complexity:** \(O((V + E) \log V)\)  
  - Each node is processed once in the worst case, and edge relaxation takes logarithmic time due to the priority queue.  
- **Space Complexity:** \(O(V + E)\)  
  - The adjacency list and distance array take \(O(V + E)\) space.  

---

## **Code**
```cpp
class Solution {
public:
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& edge : edges) {
            adj[edge[1]].push_back({edge[0], edge[2]});
        }
        
        int ans = -1;
        vector<int> dis(n, 1e9);
        set<pair<int, int>> pq;
        
        pq.insert({0, 0});
        dis[0] = 0;
        
        while (!pq.empty()) {
            auto p = *(pq.begin());
            int d = p.first;
            int node = p.second;
            pq.erase(p);
            
            for (auto& it : adj[node]) {
                if (dis[it.first] > max(d, it.second)) {
                    if (dis[it.first] != 1e9) pq.erase({dis[it.first], it.first});
                    dis[it.first] = max(d, it.second);
                    pq.insert({dis[it.first], it.first});
                }
            }
        }
        
        for (auto& it : dis) {
            if (it == 1e9) {
                ans = -1;
                break;
            } else {
                ans = max(ans, it);
            }
        }
        
        return ans;
    }
};
```

## **Key Observations**
- **Why Dijkstra?**  
  - Although this isn't a shortest-path problem, **Dijkstra’s greedy approach** ensures we find the path with the minimum maximum weight.  
- **Why `max(d, it.second)`?**  
  - Since we are interested in the max edge weight along a path, we take `max(d, it.second)` instead of summing distances.  
- **Why `set<pair<int, int>>`?**  
  - Using a **set** ensures efficient updates and retrievals in \(O(\log V)\) time.  

---


['Graph', 'Heap (Priority Queue)', 'Shortest Path', 'C++']