🧠 Think Simply: Modified Dijkstra's Beats 100%
Link to Faster Than 100% Runhttps://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph/submissions/1506924000/Core ConceptsA solid understanding of
# Link to Faster Than 100% Run
https://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph/submissions/1506924000/

# Core Concepts 
A solid understanding of the following is needed to understand the solution.

- Dijkstra's: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- minHeap: https://en.wikipedia.org/wiki/Min-max_heap

# Key Insight
- We should reverse all edges in the graph. This allows us to use `0` as the source node for Dijkstra's.

- Standard Dijksta's prioritizes the shortest path,
but we need to prioritize the path with the lowest edge-weight.

- To do this the entries in our minHeap must take the form 
  `(max_edge_weight, vertex)`
This ensures that the entry with the minimum `max_edge_weight` always gets prioritized.

- Finally, because we are only interested in the global max_edge_weight,
there is no need to store an array of the minimum weights to all verticies
as in the standard Dijkstra's.

# Complexity
- Time complexity:
$O(E + V\log(V))$

- Space complexity:
$O(E + V)$

# Code
```python3 []
class Solution:
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        """
        The Algorithm ----------------------------------------------
        1. Use modified version of Dijkstra's. Reverse all edges.
        2. Track the max_edge_weight along the path as we go (ans).
        3. In modified Dijkstra's, **prioritize paths with a low max_edge_weight**.
            NOT THE SHORTEST PATHS.
        4. In the end, validate that all nodes are reachable.
        5. If all nodes are reachable return the max_edge_weight.
        """

        adj = { i: list() for i in range(n) }
        for A, B, W in edges:
            # 1: Reverse edges
            adj[B].append((W, A))

        visited = set()

        # 2: track global max_edge weight
        ans = 0

        # 3: heap of (max_edge_weight, vertex)
        heap = [ (0, 0) ]
        while heap:
            max_edge_weight, v1 = heappop(heap)
            if v1 in visited:
                continue
            # 2: track global max_edge_weight
            ans = max(ans, max_edge_weight)
            visited.add(v1)

            for w2, v2 in adj[v1]:
                if v2 not in visited:
                    heappush(heap, (max(max_edge_weight, w2), v2))

        # 4: verify all nodes visited
        if len(visited) < n:
            return -1

        return ans


                
```
['Python3']