Leetcode 1229 Solution

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)

        for src, dst in red_edges:
            graph[(src, 'r')].append((dst, 'b'))

        for src, dst in blue_edges:
            graph[(src, 'b')].append((dst, 'r'))

        q = collections.deque()
        visited = set()
        red_min_steps = [sys.maxsize] * n
        blue_min_steps = [sys.maxsize] * n
        step = 0

        q.append((0, 'r'))
        visited.add((0, 'r'))
        red_min_steps[0] = 0

        q.append((0, 'b'))
        visited.add((0, 'b'))
        blue_min_steps[0] = 0

        while q:
            s = len(q)

            for _ in range(s):
                node_id, node_color = q.popleft()

                for neigh_node_id, neigh_node_color in graph[(node_id, node_color)]:
                    if (neigh_node_id, neigh_node_color) in visited:
                        continue

                    if neigh_node_color == 'r':
                        red_min_steps[neigh_node_id] = min(red_min_steps[neigh_node_id], step + 1)
                    else:
                        blue_min_steps[neigh_node_id] = min(blue_min_steps[neigh_node_id], step + 1)

                    q.append((neigh_node_id, neigh_node_color))
                    visited.add((neigh_node_id, neigh_node_color))

            step += 1

        ans = []
        for red_opt, blue_opt in zip(red_min_steps, blue_min_steps):
            opt = min(red_opt, blue_opt)
            if opt == sys.maxsize:
                ans.append(-1)
            else:
                ans.append(opt)

        return ans