Submission #3442902

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int f(int in){
    if(in < 10){
        return in;
    }
    return in % 10 + f(in / 10);
}

int main() {
    //cout.precision(10);
    int k;
    cin >> k;
    vector<i_i> pathes[100020];
    int cost[100020];
    for(int i = 0; i <= 100005; i++){
        cost[i] = INF;
        for(int j = 0; j < 10; j++){
            int next = i + j * k;
            pathes[i].push_back({next % 10, next / 10});
        }
        if(i > 0) pathes[i].push_back({f(i), 100005});
    }
    cost[0] = 0;
    priority_queue<i_i, vector<i_i>, greater<i_i> > search;
    search.push({0, 0});
    while(!search.empty()){
        int now = search.top().second;
        //cout << now << " " << search.top().first << endl;
        search.pop();
        if(now == 100005){
            cout << cost[now] << endl;
            return 0;
        }
        for(int i = 0; i < pathes[now].size(); i++){
            int next = pathes[now][i].second;
            int next_cost = cost[now] + pathes[now][i].first;
            if(next_cost >= cost[next]){
                continue;
            }
            cost[next] = next_cost;
            search.push({next_cost, next});
        }
    }
    return 0;
}

Submission Info

Judge Result