Do you play computer games? If yes, what is your favorite or, maybe, what category of games do you like? As for me, I like Civilization (I played parts V and VI). Also I like RPGs and strategies in common. To my mind, it is a really good way to rest. What do you think?

Введение

Недавно обнаружил, что на Codeforces нет блога с объяснением такого интересного алгоритма, как 1-K BFS. Поэтому я решил написать этот блог для тех, кто, так же как и я, любит читать туториалы именно здесь (как минимум тут есть комментарии, где можно предложить задачи или задать вопрос). Я постараюсь писать максимально понятно, но это мой первый опыт написания текста такого плана, так что не судите строго.

Алгоритм

Для тех, кто знаком с BFS (если не знакомы, рекомендую перед продолжением чтения познакомиться), я прикрепляю картинку. 1-K BFS тоже ищет кратчайшие пути и отличается от BFS лишь тем, что мы заводим массив очередей, а не одну. Для разъяснения рассмотрим следующую задачу: Дан граф на N вершинах и M рёбрах, на каждом ребре записана ненулевая цифра. Каждому пути сопоставим число, образованное цифрами на рёбрах. Необходимо для каждой вершины, кроме первой, найти минимальную сумму цифр по числам, соответствующим путям от первой до неё. N <= 10^7, M <= 5 * 10^7.

Перефразируем условие — нужно просто найти кратчайший путь от первой вершины до любой другой. Но хитрый автор задачи подобрал такие ограничения, что алгоритм Дейкстры тут не поможет. Можно заметить очень маленькое ограничение на веса рёбер — они лежат на отрезке от 1 до 9. "1-K" в названии нашего алгоритма как раз означает то, что веса рёбер лежат на отрезке от 1 до K, в нашем случае K = 9.

Сначала заведём массив из X очередей, где X — магическая величина, о которой я скажу чуть ниже, и положим стартовую вершину в нулевую очередь. Кроме того, заведем массив d[v], где мы будем хранить ответ (для начальной вершины ответ — ноль), а также массив used[v] — анализировали ли мы вершину v в алгоритме. По сути, алгоритм работает так: пусть мы смотрим на вершину u и, как и в BFS, уже знаем корректное расстояние до неё. Теперь каждую вершину w, в которую есть ребро из u, добавим в очередь под номером d[u] + <вес ребра>. Так как ребра неотрицательные, после этого расстояние до u никогда не улучшиться. Необходимо поддерживать номер очереди, на которую мы смотрим, пусть этот номер лежит в переменной pos. Для следующей итерации увеличим pos до первой непустой очереди.

Может показаться, что так как ответы могут принимать значения порядка (N — 1) * K, то и X надо взять большим. На самом же деле, достаточно взять X равным всего лишь K + 1. Почему можно так сделать? Заметим, что в каждый момент времени нам нужна только K + 1 очередь, так как мы не можем класть вершины в очереди с номерами, большими pos более чем на K. Поэтому остается дописать % (K + 1) в обращении к индексу очереди, и алгоритм готов!

Естественно, код для лучшего понимания:

        bfs[0].push(start);
	d[start] = 0;
	int pos = 0, kol = 1; // удобно ввести переменную kol - количество вершин, которые лежат в очередях
	while (kol > 0)
	{
		while (bfs[pos % (k + 1)].empty())
		{
			++pos;
		}
		int u = bfs[pos % (k + 1)].front(); 
		bfs[pos % (k + 1)].pop();
		--kol;
		if (used[u]) // уже использованная вершина может лежать в других очередях
		{
			continue;
		}
		used[u] = true;
		for (pair<int, int> edge : g[u])
		{
			int cost = edge.first, w = edge.second;
			if (d[u] + cost < d[w])
			{
				d[w] = d[u] + cost;
				bfs[d[w] % (k + 1)].push(w);
				++kol;
			}
		}
	}

Нетрудно понять, что асимптотика такого алгоритма O(N*K + M), так как после каждой из N вершин мы можем увеличить pos максимум K раз, а также мы смотрим на каждое из M ребер. Понятно также, как делать восстановление ответа — запоминаем предков при обновлении ответа.

На этом у меня всё, надеюсь, вам понравилось!