[atARC084D]Small Multiple

构造一张图：$forall x$，向$10x$连一条边权为0的边，向$x+1$连1条边权为1的边，那么0到$i$的代价即为$i$各位数字之和

考虑到我们只关心于当前点的两个特征：1.模$n$的余数（判定是否是$n$的倍数）；2.所对应的出边，那么根据模运算的性质，可以将$xequiv y(mod n)$缩为一个点，即求0到0最小的环

然后我们可以枚举最后一个点，因此即求0到任意点的最短路

可以使用Dijkstra求，也可以用01bfs，即bfs时维护双向队列，将0边拓展的加到队首，将1边拓展的加到队尾，正确性只需要归纳队列中至多仅有两种距离的点即可

#include<bits/stdc++.h>
using namespace std;
#define N 100005
deque<int>q;
int n,ans,d[N],vis[N];
int main(){
    scanf("%d",&n);
    memset(d,0x3f,sizeof(d));
    q.push_front(0);
    d[0]=0;
    while (!q.empty()){
        int k=q.front();
        q.pop_front();
        if (vis[k])continue;
        vis[k]=1;
        if (d[10*k%n]>d[k]){
            d[10*k%n]=d[k];
            q.push_front(10*k%n);
        }
        if (d[(k+1)%n]>d[k]+1){
            d[(k+1)%n]=d[k]+1;
            q.push_back((k+1)%n);        
        }
    }
    ans=d[n-1]+1;
    for(int i=1;i<n;i++)
        if (10*i%n==0)ans=min(ans,d[i]);
    printf("%d",ans);
}