#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=2e9;
int n;
struct edge{int u,v,w,nxt;}e[N*10];
int cnt,head[N];
void add(int u,int v,int w)
{
	e[++cnt]=(edge){u,v,w,head[u]};
	head[u]=cnt;
}
struct data
{
	int w,id;
	bool operator()(data x,data y){return x.w>y.w;}
};
int dis[N];
bool vis[N];
void Dijkstra()
{
	priority_queue<data,vector<data>,data>q;
	dis[0]=inf;
	for(int i=10;i<n;i++)dis[i]=inf;
	for(int i=1;i<=9;i++)q.push((data){i,i}),dis[i]=i;
	while(!q.empty())
	{
		int u=q.top().id;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(vis[v]==0)q.push((data){dis[v],v});
			}
		}
	}
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++)
		for(int j=0;j<10;j++)
			add(i,(i*10+j)%n,j);
	Dijkstra();
	printf("%d",dis[0]);
	return 0;
}

就一个最短路（很久没写了不太会），但是不知道为什么CE了，本地是能编译的。

另外，Dijkstra是能处理正边权还是非负边权