Вопрос по 0-k BFS, 27:55. Правильно ли я понимаю, что для алгоритма нам не обязательно нужен массив именно очередей? Кажется порядок обхода вершин с одинаковой длиной пути до них не принципиален, важно только чтобы все вершины с меньшей длиной пути были уже обработаны. А значит вместо очередей на основе дека можно завести стек на основе вектора. Асимптотика не изменится, но вектор должен работать чуть быстрее. Если развивать идею дальше, то вместо массива векторов можно завести одну priority_queue с парой (длина пути, вершина) и сортировкой по увеличению длины пути. Если это так, то версия с priority_queue выглядит лучше, потому что при этом потребление памяти становится что-то вроде O(E) вместо O(kE), т.е. избавляемся от лишней зависимости от входных данных и после модификации алгоритм хорошо работает и на больших k. Вопрос правда насколько измененный алгоритм все-еще может называться BFS, все-таки BFS предполагает определенный порядок обхода вершин. Однако в большинстве задач, где используется BFS, важна в первую очередь группировка вершин по расстоянию, а порядок обхода в вершин с одинаковым расстоянием часто не важен. С другой стороны версию с priority_queue легко расширить до сохранения оригинального порядка обхода, если хранить также и "время" добавления в очередь.