Ориентированный граф, время передачи по ребру t ∈ {1,2}. Сигнал стартует из вершины 0. Найти время достижения каждой вершины. Показан BFS по «бакетам расстояний» (1-k BFS): вершина на расстоянии d с ребром веса w кладётся в очередь d+w.
Идея. Обычный BFS не работает при разных весах. Берём массив очередей по расстоянию: обрабатываем вершины в порядке возрастания d. Это эквивалентно расщеплению ребра веса 2 на две единички, но без лишних вершин.