Problem:
 Score : 700 points    Problem Statement Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K .      Constraints  2 \leq K \leq 10^5  K is an integer.         Input Input is given from Standard Input in the following format:  K       Output Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K .        Sample Input 1 6      Sample Output 1 3  12=6×2 yields the smallest sum.       Sample Input 2 41      Sample Output 2 5  11111=41×271 yields the smallest sum.       Sample Input 3 79992      Sample Output 3 36

Solution (Python):
from heapq import heappush, heappop


def dijkstra(edge, start, end):
    """
    Create distance(cost) table for all nodes.
    :param edge: List of tuple(to, cost)
    :param start: start node
    :param end: end node
    :return: minimum cost from start to end
    """
    h = [(0, start)]
    used = [False] * len(edge)

    while h:
        cost, node = heappop(h)
        if used[node]:
            continue
        used[node] = True

        if node == end:
            return cost

        for i, c in edge[node]:
            heappush(h, (cost + c, i))

    return -1


K = int(input())

edge = [[] for _ in range(K)]
for i in range(1, K):
    if i % 10 != 9:
        edge[i].append(((i+1) % K, 1))
    edge[i].append(((i*10) % K, 0))

print(dijkstra(edge, 1, 0) + 1)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

k, = map(int, readline().split())

from collections import deque
INF = 1<<30
res = [INF]*k
res[1] = 1

q = deque([(1,1)])
while q:
    dv,v = q.popleft()
    if res[v] < dv: continue
    
    for to,cost in [(10*v%k,0),((v+1)%k,1)]:
        
        if dv + cost < res[to]:
            res[to] = dv + cost
            if cost: q.append((res[to],to))
            else: q.appendleft((res[to],to))
    
    
print(res[0])

Solution (Python):
from collections import *
K=int(input())
D=[K+1]*K
D[1]=1
Q=deque([1])
def bfs():
  global Q,D,K
  v=0
  while len(Q):
    v=Q.popleft()
    if D[v*10%K]>D[v]:
      D[v*10%K]=D[v]
      Q.appendleft(v*10%K)
    if D[(v+1)%K]>D[v]+1:
      D[(v+1)%K]=D[v]+1
      Q.append((v+1)%K)

bfs()
print(D[0])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

k = I()
q = deque([1])
cost = [INF] * k
cost[1] = 1
while q:
    u = q.popleft()
    if cost[u * 10 % k] > cost[u]:
        cost[u * 10 % k] = cost[u]
        q.appendleft(u * 10 % k)
    if cost[(u + 1) % k] > cost[u] + 1:
        cost[(u + 1) % k] = cost[u] + 1
        q += [(u + 1) % k]


print(cost[0])

Solution (Python):
k = int(input())
g = [[] for _ in range(k)]
for i in range(1,k):
    g[i].append([i*10%k,0])
    if i%10 != 9:
        g[i].append([(i+1)%k,1])
v = [100000]*k
v[1] = 1

def draw(d):
    for i in range(k):
        if v[i] > d:
            continue
        for v_next in g[i]:
            if v[i] == d and v_next[1] == 0 and v[v_next[0]] > d:
                v_n = v_next[0]
                while v[v_n] > d:
                    v[v_n] = d
                    v_n = v_n*10%k
            elif v[i] == d-1 and v_next[1] == 1 and v[v_next[0]] > d:
                v_n = v_next[0]
                while v[v_n] > d:
                    v[v_n] = d
                    v_n = v_n*10%k
            
for i in range(1,46):
    draw(i)
    if v[0] == i:
        print(v[0])
        exit()

Solution (Python):
import heapq

K = int(input())
D = [9999]*K
D[1] = 1
H = [(1,1)]
while len(H) != 0:
    c,h = heapq.heappop(H)
    if D[(h*10)%K] > c:
        D[(h*10)%K] = c
        H.append((c,(h*10)%K))
    if D[(h+1)%K] > c + 1:
        D[(h+1)%K] = c + 1
        H.append((c+1,(h+1)%K))

print(D[0])

Solution (Python):
from collections import deque

K = int(input())
D = [9999]*K
D[1] = 1
H = deque()
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h*10)%K] > D[h]:
        D[(h*10)%K] = D[h]
        H.append((h*10)%K)
    if D[(h+1)%K] > D[h] + 1:
        D[(h+1)%K] = D[h] + 1
        H.appendleft((h+1)%K)

print(D[0])

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

K=int(input())
pro=Dijkstra(K)
for i in range(0,K):
    pro.add(i,(i+1)%K,1)
    pro.add(i,(10*i)%K,0)

ans=pro.shortest_path(1)[0]
print(ans+1)

Solution (Python):


from collections import deque



K = int(input())


def solve():
    visit = [False] * K
    
    dq = deque([(0, 1)])
    while dq:
        s, num = dq.popleft()
        visit[num] = True
        if num == 0:
            return s
        a = num * 10 % K
        if not visit[a]:
            dq.appendleft((s, a))
        b = (num + 1) % K
        if not visit[b]:
            dq.append((s + 1, b))
    
    assert False


def main():
    ans = solve() + 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
k=int(input())
g=[[] for i in range(k)]
for i in range(k):
  g[i].append(((i+1)%k,1))
  if i:
    g[i].append((10*i%k,0))
q=deque([1])
res=[float('inf')]*k
res[1]=1
while q:
  v=q.popleft()
  if v==0:
    break
  for c,d in g[v]:
    if res[c]<=res[v]+d:
      continue
    res[c]=res[v]+d
    if d:
      q.append(c)
    else:
      q.appendleft(c)
print(res[0])

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline

K = int(readline())

inf = 10**9+7
dist = [inf]*(K+1)
dist[K] = 0
Q = deque([K])
used = [False]*(K+1)
while Q:
    vn = Q.pop()
    if used[vn]:
        continue
    used[vn] = True
    vf = (vn*10)%K
    if vn%K and not used[vf]:
        dist[vf] = min(dist[vf], dist[vn])
        Q.append(vf)
    vf = (vn+1)%K
    if not used[(vn+1)%K]:
        dist[vf] = min(dist[vf], 1+dist[vn])
        Q.appendleft(vf)
print(dist[0])

Solution (Python):
from collections import deque

k = int(input())
seen = [False]*k
dq = deque()
dq.append((1, 1))
ans = 0
while dq:
  v, s = dq.popleft()
  if seen[v]:
    continue
  seen[v] = True
  if v == 0:
    ans = s
    break
  nv1, nv2 = (v*10)%k, (v+1)%k
  dq.appendleft((nv1, s))
  dq.append((nv2, s+1))
print(ans)

Solution (Python):
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    k = int(input())
    dist = [-1] * k
    q = deque()
    q.append([1, 1])
    while q:
        d, u = q.popleft()
        if dist[u] != -1: continue
        dist[u] = d
        if u == 0:
            print(d)
            break
        v = (u + 1) % k
        if dist[v] == -1: q.append([d + 1, v])
        v = (u * 10) % k
        if dist[v] == -1: q.appendleft([d, v])

main()

Solution (Python):
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance
  

k = int(input())
MOD = k
INF = 10**9

graph = [[] for i in range(k)]
for i in range(k):
    graph[i].append((i*10%MOD, 0))
    graph[i].append(((i+1)%MOD, 1))
    
dp = dijkstra(1, graph)
print(dp[0] + 1)

Solution (Python):
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(input())
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]
d = dijkstra(N, e)
print(d.path(1, 0) + 1)

Solution (Python):
from heapq import *
from collections import deque

intinf = 10 ** 15

def bfs_01(n, graph, start):
    min_distance = [intinf] * n

    deq = deque()
    min_distance[start] = 0
    deq.append(start)

    while deq:
        src = deq.popleft()
        for dst, cost in graph[src]:
            next_d = min_distance[src] + cost
            if min_distance[dst] <= next_d:
                continue

            min_distance[dst] = next_d
            if cost == 0:
                deq.appendleft(dst)
            elif cost == 1:
                deq.append(dst)
            else:
                print('invalid cost in graph')
                raise ValueError

    return min_distance

def dijkstra(n, graph, start):
    min_distance = [intinf] * n

    
    heap = []

    heappush(heap, (0, start))
    min_distance[start] = 0

    while heap != []:
        d, src = heappop(heap)
        if min_distance[src] < d:
            continue
        for dst, cost in graph[src]:
            next_d = d + cost
            if next_d < min_distance[dst]:
                min_distance[dst] = next_d
                heappush(heap, (next_d, dst))

    return min_distance

def main():
    K = int(input())

    
    graph = [[] for _ in range(K)]

    for i in range(K):
        graph[i].append(((i+1) % K, 1))
        graph[i].append((i * 10 % K, 0))

    
    dist = bfs_01(K, graph, 1)

    print(dist[0] + 1)

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import *
from collections import deque

intinf = 10 ** 15

def bfs_01(n, graph, start):
    min_distance = [intinf] * n

    deq = deque()
    min_distance[start] = 0
    deq.append(start)

    while deq:
        src = deq.popleft()
        for dst, cost in graph[src]:
            next_d = min_distance[src] + cost
            if min_distance[dst] <= next_d:
                continue

            min_distance[dst] = next_d
            if cost == 0:
                deq.appendleft(dst)
            elif cost == 1:
                deq.append(dst)
            else:
                print('invalid cost in graph')
                raise ValueError

    return min_distance

def dijkstra(n, graph, start):
    min_distance = [intinf] * n

    
    heap = []

    heappush(heap, (0, start))
    min_distance[start] = 0

    while heap != []:
        d, src = heappop(heap)
        if min_distance[src] < d:
            continue
        for dst, cost in graph[src]:
            next_d = d + cost
            if next_d < min_distance[dst]:
                min_distance[dst] = next_d
                heappush(heap, (next_d, dst))

    return min_distance

def main():
    K = int(input())

    
    graph = [[] for _ in range(K)]

    for i in range(K):
        graph[i].append(((i+1) % K, 1))
        graph[i].append((i * 10 % K, 0))

    dist = dijkstra(K, graph, 1)
    

    print(dist[0] + 1)

if __name__ == '__main__':
    main()

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

k = int(input())

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    if i: g[i].append((10*i%k,0))


from collections import deque
q = deque([(1,1)])
res = [float("inf")]*k
res[1] = 1
while q:
    dd,v = q.popleft()
    if res[v] < dd: continue
    if v==0: break
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append((res[c],c))
        else: q.appendleft((res[c],c))

print(res[0])

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

k = int(input())

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    if i: g[i].append((10*i%k,0))


from collections import deque
q = deque([1])
res = [float("inf")]*k
res[1] = 1
while q:
    v = q.popleft()
    if v==0: break
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append(c)
        else: q.appendleft(c)

print(res[0])

Solution (Python):
import heapq as hq

k =int(input())
inf = float("inf")
dist = [inf for _ in range(k)]
dist[1]=1
start =1
q =[(1,1)]

while q:
    keta,nowmod = hq.heappop(q)
    if dist[(nowmod*10)%k]>keta:
        dist[(nowmod*10)%k]=keta
        hq.heappush(q,(keta,(nowmod*10)%k))
    if dist[(nowmod+1)%k]>keta+1:
        dist[(nowmod+1)%k]=keta+1
        hq.heappush(q,(keta+1,(nowmod+1)%k))

print(dist[0])

Solution (Python):
from collections import deque

K = int(input())
G = [-1 for k in range(K)]

Q = deque()
Q.append([1,1])
while len(Q) > 0:
    p = Q.popleft()
    x, d = p[0], p[1]
    if G[x] == -1:
        G[x] = d
        Q.append([(x+1)%K,d+1])
        Q.appendleft([(x*10)%K,d])

print(G[0])

Solution (Python):
def main():
  from collections import deque
  k=int(input())
  e=[[]for _ in range(k)]
  for i in range(k):
    e[i].extend([(i*10%k,0),(-~i%k,1)])
  q=deque([1])
  p,l,r=q.pop,q.appendleft,q.append
  f=[10**18]*k
  f[1]=1
  while q:
    v=p()
    for w,d in e[v]:
      c=f[v]+d
      if f[w]>c:
        (r,l)[d](w)
        f[w]=c
  print(f[0])
main()

Solution (Python):
def main():
  from collections import deque
  k=int(input())
  e=[[]for _ in range(k)]
  for i in range(k):
    e[i].extend([(i*10%k,0),(-~i%k,1)])
  q=deque([1])
  p,l,r=q.pop,q.appendleft,q.append
  f=[10**18]*k
  f[1]=1
  while q:
    v=p()
    for w,d in e[v]:
      c=f[v]+d
      if f[w]>c:
        (r,l)[d](w)
        f[w]=c
  print(f[0])
main()

Solution (Python):
from collections import deque

K = int(input())
D = [-1]*K
Q = deque()
Q.append([1,0])
while D[0] == -1:
    k,v = Q.popleft()
    D[k] = v
    j = (k*10)%K
    if D[j] == -1:
        Q.appendleft([j,v])
    l = (k+1)%K
    if D[l] == -1:
        Q.append([l,v+1])

print(D[0]+1)

Solution (Python):
k = int(input())
from collections import deque
dic = {1:1}
queue = deque()
queue.appendleft([1,1])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.append([v_,cost])

print(dic[0])

Solution (Python):
from collections import deque
K = int(input())
d={1:1}
q = deque()
q.append([1,1])

while q:
    a,c = q.popleft()
    a_ = (a*10)%K
    if(a_ not in d or c < d[a_]):
        d[a_]=c
        q.appendleft([a_,c])
    b_ = (a+1)%K
    if(b_ not in d or c < d[b_]):
        d[b_] = c+1
        q.append([b_,c+1])

print(d[0])

Solution (Python):
k = int(input())
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.append([v_,cost])

print(dic[0])

Solution (Python):
k = int(input())
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    if not (v+1)%k in dic or cost+1<dic[(v+1)%k]:
        dic[(v+1)%k] = cost+1
        queue.appendleft([(v+1)%k,cost+1])
    if not v*10%k in dic or cost<dic[v*10%k]:
        dic[v*10%k] = cost
        queue.append([v*10%k,cost])

print(dic[0])

Solution (Python):
from collections import deque
K = int(input())
d={1:1}
q = deque()
q.append([1,1])

while q:
    a,c = q.popleft()
    a_ = (a*10)%K
    if(a_ not in d or c < d[a_]):
        d[a_]=c
        q.appendleft([a_,c])
    b_ = (a+1)%K
    if(b_ not in d or c < d[b_]):
        d[b_] = c+1
        q.append([b_,c+1])

print(d[0])

Solution (Python):
from collections import deque
k=int(input())
q=deque([(1,1)])
v=[0]*(k+1)
while True:
    i,c=q.popleft()
    if i==0:
        break
    if v[i]:
        continue
    v[i]=True
    q.append(((i+1)%k,c+1))
    q.appendleft(((i*10)%k,c))
print(c)

Solution (Python):
from collections import deque
 

 
K = int(input())
q = deque()
q.append((1,1)) 
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = q.popleft()
  if visited[x]:
    continue
  visited[x] = True
  if x == 0:
    ans = s
    break
  q.appendleft((s,(10*x)%K))
  q.append((s+1,(x+1)%K))
 
print(ans)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

K=INT()

que=deque()
que.append((1, 1))
costs=[-1]*K

while len(que):
    cur,cost=que.popleft()
    if costs[cur]==-1:
        costs[cur]=cost
        que.appendleft((cur*10%K, cost))
        que.append(((cur+1)%K, cost+1))
print(costs[0])

Solution (Python):
from collections import deque
K = int(input())

cost = [None] * K
Q = deque()
Q.append((1, 1))
while Q:
    currentCost, currentNode = Q.popleft()
    if cost[currentNode] == None:
        cost[currentNode] = currentCost
        Q.append((currentCost + 1, (currentNode + 1) % K))
        Q.appendleft((currentCost, (currentNode * 10) % K))
print(cost[0])

Solution (Python):
from collections import deque

def solve(k):
    que = deque()
    que.append((1, 1))
    dp = {1: 1}
    while que:
        x, c = que.pop()
        y = (x + 1) % k
        if (not y in dp) or (dp[y] > c + 1):
            dp[y] = c + 1 
            que.appendleft((y, c+1))
        z = (10 * x) % k
        if (not z in dp) or (dp[z] > c):
            dp[z] = c
            que.append((z, c))
    return dp[0]

k = int(input())
print(solve(k))

Solution (Python):
from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if visited[n]:
            continue
        visited[n] = True
        if n == 0:
            print(s)
            return
        q.appendleft((n*10 % K, s))
        q.append(((n+1) % K, s+1))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque([[1, 1]])
    d = {1: 1}
    while q:
        n, c = q.popleft()
        a = (n * 10) % N
        if a not in d or d[a] > c:
            d[a] = c
            q.appendleft([a, c])

        b = (n + 1) % N
        if b not in d or d[b] > c+1:
            d[b] = c + 1
            q.append([b, c+1])

    print(d[0])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
k = int(input())
dis = [float("inf") for _ in range(k)]

def bfs(start, goal):
	que = deque([[start, 1]])
	while que:
		label = que.pop()
		l, c = label[0], label[1]
		if l == goal:
			return c
		if dis[l] > c:
			dis[l] = c
			que.append([(l*10)%k, c])
			que.appendleft([(l+1)%k, c+1])

print(bfs(1, 0))

Solution (Python):


def main():
    K = int(input())

    d = [100] * K
    d[1] = 1
    Q = []
    for i in range(45 + 1):
        Q.append([])
    Q[1].append(1)
    for i in range(1, 45 + 1):
        q = Q[i]
        while 0 < len(q):
            v = q.pop(0)
            nv = (v * 10) % K
            if i < d[nv]:
                d[nv] = i
                q.append(nv)
            nnv = (v + 1) % K
            if i + 1 < d[nnv]:
                d[nnv] = i + 1
                Q[i + 1].append(nnv)



    print(d[0])


if __name__ == '__main__':
    main()