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?

Introduction

I recently noticed, that there is no Codeforces blog with explanation of 1-K BFS algorithm. So, I decided to create this blog for those, who likes reading tutorials here (like me).

Algorithm

If you are familiar with BFS (if not, I recommend to do it before reading), look at the picture. 1-K BFS also finds the shortest path in the graph, like BFS, and the only difference is that we have several queues. Let's look at this problem: Given graph with N vertexes and M edges, there's one non-zero digit on every edge. Every path corresponds to number formed by digits on edges. For each vertex, except the first, find the minimum sum of digits by the numbers corresponding to the paths from the first to it. N <= 10^7, M <= 5 * 10^7.

Let's rephrase the statement: "For each vertex, except the first, find the shortest path from the first to it". But restrictions don't allow us to use Dijkstra. Despite this, you can notice a very low restriction for edge weights — they belong to the segment [1;9]. "1-K" in the name of the algorithm means that exactly (here, K = 9).

Firstly, let's define an array of X queues, where X is a magic value, about which I'll tell a bit later, and push the first vertex to the 0's queue. Moreover, let's define an array d[v] — the answer for v (d[start] = 0) and an array used[v] — was v already used or not. So, if we're currently looking at vertex u and know the correct answer for it, we need to push each vertex w that u is connected to, to the (d[u] + "edge weight")'s queue. Because weights are positive, d[u] will never become better. We need to keep the position of queue, which we're currently analyzing, for example, in variable pos. We will increase it to the index of first non-empty queue in the beginning of every iteration.

It may seem, that X is pretty big, because answer can be equal to (N — 1) * K for some vertexes. But the magic is, that X can be equal K + 1. Why can we do that? At every moment, we need only K + 1 queues, because we cannot push vertexes to queues, which index is larger pos by more than K. So, just write % (K + 1) in [] and algorithm is ready!

Code for better understanding:

        bfs[0].push(start);
	d[start] = 0;
	int pos = 0, num = 1; // I recommend to define a variable num - the number of vertexes that are in the queues
	while (num > 0)
	{
		while (bfs[pos % (k + 1)].empty())
		{
			++pos;
		}
		int u = bfs[pos % (k + 1)].front(); 
		bfs[pos % (k + 1)].pop();
		--num;
		if (used[u]) // used vertex can be in other queues
		{
			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);
				++num;
			}
		}
	}

It is easy to understand, that time complexity of this algorithm is O(N*K + M), because after analyzing each vertex we can increase pos only K times, also we have to remember about M edges.

That's all, hope you enjoyed!

P.S. Sorry for my bad English, if you find any mistake, please, contact me.