题意：
给定k，要求在k的所有倍数中，找到一个数位和最小的倍数， 输出最小数位和。
数据范围：2<=k<=1e5
解法：
考虑构造每一位的数字
,
一开始为空
,如果下一位为x
,那么数位和
+x
,
因为要是k的倍数
,那么在模k意义下计算数位和
,
那么最后一定是
%k
=0.
对于
[0,k
-1]的每个点x
:
x向x
*10%k建立一条边权为
0的边
,表示下一位选择
0,
x向
(x
*10+1)%k建立一条边权为
1的边
,表示下一位选择
1,
...
第一个数只能选
[1,9]不能选
0,否则就是前导零了
,
建立新源点S
,对
[1,9]连边
,
那么S到
0的最短路就是答案
,
因为模k意义下等于
0的就是
0的倍数
,边权和就是最小数位和
.
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define PI pair<int,int>
const int maxm
=2e5+5;
vector
<PI
>g
[maxm
];
int mark
[maxm
];
int d
[maxm
];
int k
;
int S
;
void spfa(){
queue
<int>q
;
q
.push(S
);
for(int i
=0;i
<=k
;i
++){
d
[i
]=1e18;
}
d
[S
]=0;
mark
[S
]=1;
while(!q
.empty()){
int x
=q
.front();q
.pop();
mark
[x
]=0;
for(auto i
:g
[x
]){
int v
=i
.first
,w
=i
.second
;
if(d
[v
]>d
[x
]+w
){
d
[v
]=d
[x
]+w
;
if(!mark
[v
]){
mark
[v
]=1;
q
.push(v
);
}
}
}
}
}
signed main(){
cin
>>k
;
S
=k
;
for(int i
=1;i
<10;i
++){
g
[S
].push_back({i
%k
,i
});
}
for(int i
=1;i
<k
;i
++){
for(int j
=0;j
<10;j
++){
g
[i
].push_back({(i
*10+j
)%k
,j
});
}
}
spfa();
cout
<<d
[0]<<endl
;
return 0;
}
