Задача 10 — Кратчайший путь с чередованием цветов рёбер
Ориентированный граф, каждое ребро синее или красное. Для каждой вершины найти длину кратчайшего пути из вершины 0, где цвета рёбер вдоль пути чередуются.
Идея. Состояние = (вершина, цвет последнего ребра). Из состояния (v, red) можно идти только по синим рёбрам в (u, blue) и наоборот. Это обычный BFS по удвоенному графу состояний размера 2·|V|. Ответ для вершины = min по двум её состояниям.