[Python] Binary Search / Prim
Solution 1: Binary SearchGiven the max weight maxw,
check if we can starting from 0,
reversly reach all node.Binary find the minimum maxw that can reach all nod
# **Solution 1: Binary Search**
Given the max weight `maxw`,
`check` if we can starting from `0`,
reversly reach all node.

Binary find the minimum `maxw` that can reach all nodes.

Time `O(mlogw)`
Space `O(m)`
<br>


```py [Python3]
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        G = [{} for i in range(n)]
        for i,j,w in edges:
            G[j][i] = min(G[j].get(i, inf), w)
        def check(maxw):
            bfs = [0]
            seen = [1] + [0] * (n - 1)
            for i in bfs:
                for j in G[i]:
                    if G[i][j] > maxw: continue
                    if seen[j] == 1: continue
                    bfs.append(j)
                    seen[j] = 1
            return all(seen)
        res = bisect_left(range(10 ** 6 + 1), 1, key=check)
        return res if res <= 10 ** 6 else -1
```

# **Solution 2: Prim**
Time `O(mlogm)`
Space `O(m)`
<br>

```py [Python3]
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        G = [{} for i in range(n)]
        for i,j,w in edges:
            G[j][i] = min(G[j].get(i, inf), w)
        h = [[0, 0]]
        seen = [inf] * n
        k = n
        while h and k > 0:
            d, i = heappop(h)
            if seen[i] < inf: continue
            k -= 1
            seen[i] = d
            for j in G[i]:
                if seen[j] < inf: continue
                heappush(h, [G[i][j], j])
        return -1 if k > 0 else max(seen)
```




['Binary Search', 'Shortest Path', 'Python3']