【题意】求一个k的倍数使其数位和最小，输出数位和，k<=10^5。
【算法】最短路
【题解】考虑极端情况数字是可能爆long long的（例如k*num=100...000），所以确定基本方向是依次考虑答案x的每个数位。
考虑x初始是1~9，每次在后面加一位，就有x*10+0~9十种操作。
但是x可以无限大，而且x必须是k的倍数这点很难实现，综合这两点可以考虑%k。
进一步发现，%k意义下同余的数字是等价的，也就是%k等于同一个数的x只需要保留数字和最小的。
那么就可以得到算法：
k个点表示%k=0~k-1的最小数字和，起点是1~k-1（d[i]=i），终点为0，x向(x*10+0~9)%k连边权为0~9的边，跑最短路。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=,maxm=,inf=0x3f3f3f3f;
int n,m,first[maxn],tot,d[maxn],s,t;
//dijkstra---
struct edge{int from,v,w;}e[maxm];
struct Node{
int x,d;
bool operator <(const Node &b)const{
return d>b.d;
}
}cyc;
priority_queue<Node>q;
void insert(int u,int v,int w)
{tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
int dijkstra()
{
memset(d,0x3f,sizeof(d));
d[s]=;q.push((Node){s,d[s]});
while(!q.empty())
{
cyc=q.top();q.pop();
if(cyc.d!=d[cyc.x])continue;
int x=cyc.x;
for(int i=first[x];i;i=e[i].from)
if(d[e[i].v]>d[x]+e[i].w)
{
d[e[i].v]=d[x]+e[i].w;
q.push((Node){e[i].v,d[e[i].v]});
}
}
return d[t];
}
//dijsktra---
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)for(int j=;j<=;j++)insert(i,((i-)*+j)%n+,j);
for(int j=;j<=;j++)insert(,j+,j);
s=;t=;
printf("%d",dijkstra());
return ;
}
按数位考虑的思想和取模为倍数的思想。