题意：给定一个正整数K，求K的倍数中，各位上的数字之和最小是多少？
思路非常巧妙，对于一个数，我们有定义两种改变方式：
1.加1，则数字之和+1（9的情况另行考虑）
2.乘10，数字之和不变
对于末位9的情况，我们可以归化为第二种。
于是将x到x+1连一条权值为1的边，x到x*10连一条权值为0的边，最后再模K意义下跑一边1到0的最短路即可
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define MAXN 100000+10
const int INF=;
struct Ed{
int u,dis;
Ed(){}
Ed(int u,int dis):u(u),dis(dis){}
bool operator >(const Ed &a)const{return dis>a.dis;}
};
typedef __gnu_pbds::priority_queue<Ed,greater<Ed>,__gnu_pbds::thin_heap_tag> heap;
heap q;
heap::point_iterator it[MAXN];
int k,vis[MAXN],dis[MAXN];
void dijkstra(){
for(int i=;i<k;i++)dis[i]=INF;
dis[]=;
for(int i=;i<k;i++)it[i]=q.push((Ed){i,dis[i]});
while(!q.empty()){
int t,u=q.top().u;
q.pop();
if(vis[u])continue;
vis[u]=;
t=u*%k;
if(!vis[t]&&dis[u]<dis[t]){
dis[t]=dis[u];
q.modify(it[t],(Ed){t,dis[t]});
}
t=(u+)%k;
if(!vis[t]&&dis[u]+<dis[t]){
dis[t]=dis[u]+;
q.modify(it[t],(Ed){t,dis[t]});
}
}
}
int main(){
scanf("%d",&k);
dijkstra();
printf("%d\n",dis[]+);
return ;
}