原题大意

给一个数K，在K的整数倍里，找出数位和最小的，并输出和

算法分析

首先引入图论，求一个数的数位和，可以看成一张有向图求最短路，图上的每个顶点都是整数，起点是1，数字v到数字v+1之间的值为1，数字v到数字v*10的值为0，求x的数位和就是求1到x的最短路的距离加上1。

这里求K的整数倍，可以把图压缩到K个点，因为如果两个数mod K的值相同，我们可以认为是同一个点（如2 和 20 mod 6），所以就是求从1到0的最短路。
因为只含有1和0，所以可以用双端队列来优化（每个值取出来要么不变，要么加1，不变的放到队首，加1的放到队尾，队列里的值一定是非递减的）。

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+50;
typedef pair<int, int> ii;
int solve(int K){
    deque<ii> dq;
    vector<int> vis(K, 0);
    dq.push_front(ii(1,1));
    while(!dq.empty()){
        ii p = dq.front(); dq.pop_front();
        int curr = p.first, cnt = p.second;
        if(curr == 0) return cnt;

        vis[curr] = 1;
        int next = (curr+1) % K;
        if(vis[next] == 0)
            dq.push_back(ii(next, cnt+1));

        next = (curr * 10) % K;
        if(vis[next] == 0)
            dq.push_front(ii(next, cnt));
    }
}
int main(){ 
    int K; cin >> K;
    cout << solve(K) << endl;
    return 0;
}