Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

👨‍💻 Алгоритм:

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив 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;
};

Ставь 👍 и забирай 📚 Базу знаний