AtCoder Regular Contest 084D: Small Multiple

https://beta.atcoder.jp/contests/arc084/tasks/arc084_b

iからi+1に移動する際、cost 1で、i*10に移動する際cost 0と考えてiのmodKのグラフで最短経路長を求めればいいです。
と言われると簡単だけど絶対本番思いつかない。

解説に01bfsとかいうのが載っていたのでそれで実装しました。queue内は必ず最短経路長が短い順番で並ぶので、各頂点について1回の更新しか行われないのがポイントです。計算量は結局辺の数で決まります。ダイクストラはそれを実現させるため頂点に加え、長さも持っているんですね。

int K;
int d[100010];

void solve() {
	cin >> K;
	fill(d, d + K, inf);
	d[1] = 1;
	deque<int> que;
	que.push_front(1);
	while(!que.empty()) {
		int v = que.front(); que.pop_front();
		int to = (v + 1) % K;
		// if(d[v] != inf) continue; //don't need this kind of things
		if(d[to] > d[v] + 1) {
			d[to] = d[v] + 1;
			que.push_front(to);
		}
		to = (v * 10) % K;
		if(d[to] > d[v]) {
			d[to] = d[v];
			que.push_back(to);
		}
	}
	cout << d[0] << "\n";
}