Задача: 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 и добавьте соседа в очередь.

😎 Решение:

class Solution {
    function shortestAlternatingPaths($n, $redEdges, $blueEdges) {
        $adj = [];
        foreach ($redEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 0];
        }
        foreach ($blueEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 1];
        }

        $answer = array_fill(0, $n, -1);
        $visit = array_fill(0, $n, [false, false]);
        $queue = [[0, 0, -1]];
        $answer[0] = 0;
        $visit[0][0] = true;
        $visit[0][1] = true;

        while ($queue) {
            list($node, $steps, $prevColor) = array_shift($queue);
            if (!isset($adj[$node])) continue;
            foreach ($adj[$node] as $nei) {
                list($neighbor, $color) = $nei;
                if (!$visit[$neighbor][$color] && $color != $prevColor) {
                    if ($answer[$neighbor] == -1) {
                        $answer[$neighbor] = $steps + 1;
                    }
                    $visit[$neighbor][$color] = true;
                    $queue[] = [$neighbor, $steps + 1, $color];
                }
            }
        }
        return $answer;
    }
}

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