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

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

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

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

1 #include
2 using namespace std;
3 #define N 100005
4 dequeq;
5 int n,ans,d[N],vis[N];
6 int main(){
7 scanf("%d",&n);
8 memset(d,0x3f,sizeof(d));
9 q.push_front(0);
10 d[0]=0;
11 while (!q.empty()){
12 int k=q.front();
13 q.pop_front();
14 if (vis[k])continue;
15 vis[k]=1;
16 if (d[10*k%n]>d[k]){
17 d[10*k%n]=d[k];
18 q.push_front(10*k%n);
19 }
20 if (d[(k+1)%n]>d[k]+1){
21 d[(k+1)%n]=d[k]+1;
22 q.push_back((k+1)%n);
23 }
24 }
25 ans=d[n-1]+1;
26 for(int i=1;i<n;i++)
27 if (10*i%n==0)ans=min(ans,d[i]);
28 printf("%d",ans);
29 }