BFS or Union-Find
Intuition\nThe more edges we include in a path, the smaller the cost. So for a pair of queries [a,b], if a and b belong to the same connected component (CC), th
# Intuition\nThe more edges we include in a path, the smaller the cost. So for a pair of queries `[a,b]`, if `a` and `b` belong to the same connected component (CC), the min-cost walk is the bit-wise AND of all edge weights in the CC. Otherwise, the min-cost walk is `-1`.\n\nOne edge case: if `a == b`, min-cost walk is apparently `0` (unfortunately the problem statement didn\'t seem to well-define this case)\n\nThere are two ways to get all CCs of a graph:\n1. for each node, do BFS, and keep track of the bit-wise AND of all edges. Do not re-do BFS for a node that\'s already covered by a previous BFS.\n2. Or, use Union-Find, while tracking the bit-wise AND of all edges in the same CC.\n\n# Complexity\n- Time complexity:\nO(n+m) for BFS, or O(m * Ackermann(n)), where Ackermann(n) is almost constant.\n\n- Space complexity:\nO(n)\n\n# Code\nBFS solution:\n```\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n        graph = defaultdict(list)\n        for a, b, w in edges:\n            graph[a].append((b, w))\n            graph[b].append((a, w))\n        \n        n2c = {} # node to cluster_id\n        c2v = {} # cluster_id to bit-wise-AND of all edges in it\n        \n        def bfs(node, cid):\n            val = (1 << 17) - 1\n            n2c[node] = cid\n            queue = [node]\n            while queue:\n                cur = queue.pop()\n                for nb, w in graph[cur]:\n                    val &= w\n                    if nb not in n2c:\n                        n2c[nb] = cid\n                        queue.append(nb)\n            c2v[cid] = val\n        \n        cluster_id = 0\n        for i in range(n):\n            if i not in n2c:\n                bfs(i, cluster_id)\n                cluster_id += 1\n        \n        res = []\n        for a, b in query:\n            if a == b:\n                res.append(0)\n            elif n2c[a] != n2c[b]:\n                res.append(-1)\n            else:\n                res.append(c2v[n2c[a]])\n        return res\n```\nUnion-Find solution:\n```\nclass UF:\n    def __init__(self, n):\n        self.par = list(range(n))\n        self.depth = [1] * n\n        self.val = [(1 << 17) - 1] * n\n    \n    def union(self, i, j, w):\n        ri = self.find(i)\n        rj = self.find(j)\n        val = self.val[ri] & self.val[rj] & w\n        if self.depth[ri] >= self.depth[rj]:\n            self.par[rj] = ri\n            self.val[ri] = val\n            if self.depth[ri] == self.depth[rj]:\n                self.depth[ri] += 1\n        else:\n            self.par[ri] = rj\n            self.val[rj] = val\n            \n    def find(self, i):\n        if self.par[i] == i:\n            return i\n        self.par[i] = self.find(self.par[i])\n        return self.par[i]\n    \n    def get_val(self, i):\n        return self.val[self.find(i)]\n        \n\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n        uf = UF(n)\n        for a, b, w in edges:\n            uf.union(a, b, w)\n        \n        res = []\n        for a, b in query:\n            if a == b:\n                res.append(0)\n            elif uf.find(a) == uf.find(b):\n                res.append(uf.get_val(a))\n            else:\n                res.append(-1)\n        return res\n```
['Breadth-First Search', 'Union Find', 'Python3']