Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

class Solution {
    function numBusesToDestination($routes, $source, $target) {
        if ($source == $target) return 0;

        $adjList = [];
        foreach ($routes as $route => $stops) {
            foreach ($stops as $stop) {
                if (!isset($adjList[$stop])) {
                    $adjList[$stop] = [];
                }
                $adjList[$stop][] = $route;
            }
        }

        $q = [];
        $vis = [];
        foreach ($adjList[$source] ?? [] as $route) {
            $q[] = $route;
            $vis[$route] = true;
        }

        $busCount = 1;
        while (count($q) > 0) {
            $size = count($q);
            for ($i = 0; $i < $size; $i++) {
                $route = array_shift($q);
                foreach ($routes[$route] as $stop) {
                    if ($stop == $target) return $busCount;
                    foreach ($adjList[$stop] ?? [] as $nextRoute) {
                        if (!isset($vis[$nextRoute])) {
                            $vis[$nextRoute] = true;
                            $q[] = $nextRoute;
                        }
                    }
                }
            }
            $busCount++;
        }
        return -1;
    }
}

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