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"; }