1129. Shortest Path with Alternating Colors

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        var adj = new Dictionary<int, List<(int, int)>>();
        foreach (var edge in redEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 0));
        }
        foreach (var edge in blueEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 1));
        }
        var answer = new int[n];
        Array.Fill(answer, -1);
        var visit = new bool[n, 2];
        var queue = new Queue<(int node, int steps, int prevColor)>();
        queue.Enqueue((0, 0, -1));
        answer[0] = 0;
        visit[0, 0] = true;
        visit[0, 1] = true;
        while (queue.Count > 0) {
            var (node, steps, prevColor) = queue.Dequeue();
            if (!adj.ContainsKey(node)) continue;
            foreach (var (neighbor, color) in adj[node]) {
                if (!visit[neighbor, color] && color != prevColor) {
                    if (answer[neighbor] == -1) answer[neighbor] = steps + 1;
                    visit[neighbor, color] = true;
                    queue.Enqueue((neighbor, steps + 1, color));
                }
            }
        }
        return answer;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        var adj = new unordered_map<int, List<(int, int)>>();
        foreach (var edge in redEdges) {
            if (!adj.count(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].push_back((edge[1], 0));
        }
        foreach (var edge in blueEdges) {
            if (!adj.count(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].push_back((edge[1], 1));
        }
        var answer = new int[n];
        Array.Fill(answer, -1);
        var visit = new bool[n, 2];
        var queue = new queue<(int node, int steps, int prevColor)>();
        queue.Enqueue((0, 0, -1));
        answer[0] = 0;
        visit[0, 0] = true;
        visit[0, 1] = true;
        while (queue.size() > 0) {
            var (node, steps, prevColor) = queue.Dequeue();
            if (!adj.count(node)) continue;
            foreach (var (neighbor, color) in adj[node]) {
                if (!visit[neighbor, color] && color != prevColor) {
                    if (answer[neighbor] == -1) answer[neighbor] = steps + 1;
                    visit[neighbor, color] = true;
                    queue.Enqueue((neighbor, steps + 1, color));
                }
            }
        }
        return answer;
    }
}

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] redEdge : redEdges) {
            adj.computeIfAbsent(redEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(redEdge[1], 0));
        }

        for (int[] blueEdge : blueEdges) {
            adj.computeIfAbsent(blueEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(blueEdge[1], 1));
        }

        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        boolean[][] visit = new boolean[n][2];
        Queue<int[]> q = new LinkedList<>();

        q.offer(new int[] { 0, 0, -1 });
        answer[0] = 0;
        visit[0][1] = visit[0][0] = true;

        while (!q.isEmpty()) {
            int[] element = q.poll();
            int node = element[0], steps = element[1], prevColor = element[2];

            if (!adj.containsKey(node)) {
                continue;
            }

            for (List<Integer> nei : adj.get(node)) {
                int neighbor = nei.get(0);
                int color = nei.get(1);
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1)
                        answer[neighbor] = 1 + steps;
                    visit[neighbor][color] = true;
                    q.offer(new int[] { neighbor, 1 + steps, color });
                }
            }
        }
        return answer;
    }
}

var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
    const adj = new Map();
    for (const [a, b] of redEdges) {
        if (!adj.has(a)) adj.set(a, []);
        adj.get(a).push([b, 0]);
    }
    for (const [u, v] of blueEdges) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u).push([v, 1]);
    }

    const answer = Array(n).fill(-1);
    const visit = Array.from({ length: n }, () => [false, false]);
    const queue = [[0, 0, -1]];
    answer[0] = 0;
    visit[0][0] = visit[0][1] = true;

    while (queue.length) {
        const [node, steps, prevColor] = queue.shift();
        if (!adj.has(node)) continue;
        for (const [neighbor, color] of adj.get(node)) {
            if (!visit[neighbor][color] && color !== prevColor) {
                if (answer[neighbor] === -1) {
                    answer[neighbor] = steps + 1;
                }
                visit[neighbor][color] = true;
                queue.push([neighbor, steps + 1, color]);
            }
        }
    }
    return answer;
};

from collections import deque, defaultdict

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        adj = defaultdict(list)
        for a, b in redEdges:
            adj[a].append((b, 0))
        for u, v in blueEdges:
            adj[u].append((v, 1))
        
        answer = [-1] * n
        visit = [[False, False] for _ in range(n)]
        queue = deque([(0, 0, -1)])
        answer[0] = 0
        visit[0][0] = visit[0][1] = True
        
        while queue:
            node, steps, prevColor = queue.popleft()
            
            for neighbor, color in adj[node]:
                if not visit[neighbor][color] and color != prevColor:
                    if answer[neighbor] == -1:
                        answer[neighbor] = steps + 1
                    visit[neighbor][color] = True
                    queue.append((neighbor, steps + 1, color))
        
        return answer

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
    adj := make(map[int][][]int)
    for _, edge := range redEdges {
        adj[edge[0]] = append(adj[edge[0]], []int{edge[1], 0})
    }
    for _, edge := range blueEdges {
        adj[edge[0]] = append(adj[edge[0]], []int{edge[1], 1})
    }

    answer := make([]int, n)
    for i := range answer {
        answer[i] = -1
    }
    visit := make([][2]bool, n)
    queue := [][3]int{{0, 0, -1}}
    answer[0] = 0
    visit[0][0] = true
    visit[0][1] = true

    for len(queue) > 0 {
        node, steps, prevColor := queue[0][0], queue[0][1], queue[0][2]
        queue = queue[1:]
        for _, nei := range adj[node] {
            neighbor, color := nei[0], nei[1]
            if !visit[neighbor][color] && color != prevColor {
                if answer[neighbor] == -1 {
                    answer[neighbor] = steps + 1
                }
                visit[neighbor][color] = true
                queue = append(queue, [3]int{neighbor, steps + 1, color})
            }
        }
    }
    return answer
}

Algorithm

Создание структуры данных и инициализация:

Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.

Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.

Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

Инициализация очереди и начальных условий:

Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).

Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

Обработка очереди и обновление результата:

Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).

Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎