# Leetcode 1229 Solution

https://leetcode.com/problems/shortest-path-with-alternating-colors

## 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'))
red_min_steps[0] = 0

q.append((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))