AtCoder Beginner Contest 077 D - Small Multiple

AtCoder Beginner Contest 077 D - Small Multiple

题意： 给定一个 $K$ ，要求你从 $K$ 的所有倍数中包括 $K$ 自身，找到一个数，他的所有数位和是所有 $K$ 的倍数中最小的。

思路： 该题本质是一个图论问题，我们需要建立起模型。首先观察他的性质，我们从位上来观察，发现无论 $K$ 是什么，我们都可以从 $1$ 开始通过 $x+1$ 或者 $x\ast 10$ 两个操作使得 $1$ 成功到达 $K$ ，而一旦 $x>=k$ 之后会发生什么呢？很容易又发现重新进入了从 $1$ 到 $K$ 的循环 。因此我们可以从 $1$ 开始枚举到 $K-1$ ，每个数可以建立两条边，分别是$i+1$$mod$$K$ 权值为 $1$ 和 $i+10$$mod$$K$ 权值为 $0$ 。因此总边数最多为 $2K$ 条，最后跑一遍 $1$$\Rightarrow$$0$ 的短路即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int,int>PII;
int n;
const int N = 1e5+10;
int h[N],e[N<<1],ne[N<<1],idx,w[N<<1];
int d[N];
bool st[N];
void add(int a,int b,int c){
    
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dijkstra(){
    
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    memset(d,0x3f,sizeof d);
    d[1]=0;
    heap.push({
    0,1});
    while(heap.size()){
    
        auto x=heap.top();
        heap.pop();
        int ver=x.second,distance=x.first;
        if(st[ver])continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i]){
    
            int j=e[i];
            if(d[j]>d[ver]+w[i]){
    
                d[j]=d[ver]+w[i];
                if(!st[j]){
    
                    heap.push({
    d[j],j});
                }
            }
        }
    }
    return d[0];
}
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
    //建图
        add(i%n,(i+1)%n,1);
        add(i%n,(i*10)%n,0);
    }
    cout<<1+dijkstra()<<endl;
    return 0;
}