ARC 084 D Small Multiple

##問題
https://atcoder.jp/contests/arc084/tasks/arc084_b
##見た感じ
全然検討が付かなくて、普通に倍数だけを探索すれば、最悪$10^{13}$個の整数を探索せんといけんやんってなりました。
実はそんなことはなくて、桁の和が増えていく方向に探索していけば、とける問題であれば間に合うということで、
以下の操作を使って、整数を探索していきます。

1. 1を足す
2. 10倍する

これらの操作を順次使ってdijkstraすれば桁の和が単調に（しかも1ずつ！）増える方向に探索できます。$k$の倍数に到達したら、探索終了です。
ここで、この操作で重要なのは、$k$の倍数に到達したかどうかを判定できればいいので、modの世界でノードを0~k-1まで用意してそこで推移させればよろしい。
##解法
ノード1からノード0までの最短路を計算
##ソースコード

const int N_MAX=100005;
int k;

ll dijkstra(){
    vll v(k,INF18);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> que;
    que.push({0,1});
    v[1]=0;
    while(que.size()){
        pair<ll,int> now=que.top();que.pop();
        if(now.first>v[now.second])continue;
        if(now.second%10!=9){
            if(minin(v[(now.second+1)%k],v[now.second]+1)){
                que.push({v[now.second]+1,(now.second+1)%k});
            }
        }
        if(minin(v[(now.second*10)%k],v[now.second])&&(now.second*10)%k!=now.second){
            que.push({v[now.second],(now.second*10)%k});
        }
    }
    return v[0]+1;
}

void Main(){
    int x=0,y=INF10,z=1;
    //入力
    cin>>k;
    //処理
    auto ans=dijkstra();
    //出力
    cout << ans <<endl;
}

int main(){
    cin.tie(nullptr);
    cout<<fixed<<setprecision(12);
    Main();
}