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 collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
    mat.append([])

dis = [10**18]*k
dis[1] = 0
for i in range(k):
    mat[i].append(((i+1)%k,True))

    if (10*i)%k != i:
        mat[i].append(((10*i)%k,False))


d.append(1)
res = 0
while d:
    left = d.popleft()
    for neighbour,edge in mat[left]:
        distance = edge + dis[left]
        if dis[neighbour] > distance: 
            dis[neighbour] = distance 
            
            if edge == 0:
                d.appendleft(neighbour)
            else:
                d.append(neighbour)
print(dis[0]+1)

Solution (Python):
from collections import deque


def solve(K):
    s = 1
    q = deque()
    q.append(s)
    dists = {}
    dists[s] = 1
    while len(q) > 0:
        n = q.pop()
        if n == 0:
            break
        m = (n*10)%K
        if m not in dists:
            dists[m] = dists[n]
            q.append(m)
        elif dists[m] > dists[n]:
            dists[m] = dists[n]
            q.append(m)
        if n % 10 != 9:
            m = (n+1)%K
            if m not in dists:
                dists[m] = dists[n] + 1
                q.appendleft(m)
            elif dists[m] > dists[n] + 1:
                dists[m] = dists[n] + 1
                q.appendleft(m)
    return dists[0]


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


if __name__ == '__main__':
    main()

Solution (Python):
import queue


def bfs01(s: int, t: int, V: int, graph: list)->int:
    '''01-bfs
    :param s: source
    :param t: sink
    :param V: number of vertex
    :param graph: graph
    :return: minimum distance from `s` to `t`
    '''
    INF = float('inf')

    
    q = queue.deque([])  
    qc = 0               
    l = [INF] * V        

    
    q.append(s)
    qc += 1
    l[s] = 0

    
    
    
    
    
    while qc > 0:
        u = q.popleft()
        qc -= 1
        for v, c in graph[u]:
            if l[u] + c < l[v]:
                l[v] = l[u] + c
                qc += 1
                if c == 0:
                    q.appendleft(v)
                else:
                    q.append(v)

    return l[t]


def small_multiple(K: int)->int:
    graph = []
    for k in range(K):
        
        
        graph.append([])
        v1 = k+1 if k+1 < K else 0
        v10 = (k*10) % K

        graph[k].append((v1, 1))
        if v10 != k:
            graph[k].append((v10, 0))

    return bfs01(1, 0, K, graph) + 1


if __name__ == "__main__":
    K = int(input())
    ans = small_multiple(K)
    print(ans)

Solution (Python):
import queue


def bfs01(s: int, t: int, V: int, graph: list)->int:
    INF = float('inf')

    q = queue.deque([])
    qc = 0
    l = [INF] * V

    q.append(s)
    qc += 1
    l[s] = 0

    while qc > 0:
        u = q.popleft()
        qc -= 1
        for v, c in graph[u]:
            if l[u] + c < l[v]:
                l[v] = l[u] + c
                qc += 1
                if c == 0:
                    q.appendleft(v)
                else:
                    q.append(v)

    return l[t]


def small_multiple(K: int)->int:
    graph = []
    for k in range(K):
        graph.append([])
        v1 = k+1 if k+1 < K else 0
        v10 = (k*10) % K

        graph[k].append((v1, 1))
        if v10 != k:
            graph[k].append((v10, 0))

    return bfs01(1, 0, K, graph) + 1


if __name__ == "__main__":
    K = int(input())
    ans = small_multiple(K)
    print(ans)

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 defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    s = S()
    t = S()
    if s+t == t[::-1]+s[::-1]:
        print("YES")
    else:
        print("NO")


def B():
    n = I()
    for i in range(int(n**0.5)+2)[::-1]:
        if i*i <= n:
            print(i*i)
            quit()

def C():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    q = [0 for i in range(n)]
    ans = 0
    a.sort()
    b.sort()
    c.sort()
    for i in range(n):
        j = bisect.bisect_left(a,b[i])
        q[i] = j
    for i in range(n-1):
        q[i+1] += q[i]
    q.insert(0,0)
    for i in range(n):
        j = bisect.bisect_left(b,c[i])
        ans += q[j]
    print(ans)

def D():
    def dijkstra():
        d = [float("inf") for i in range(k)]
        q = [[0,1]]
        d[1] = 0
        while q:
            dx,x = heappop(q)
            for y,dy in v[x]:
                if d[y] > dx+dy:
                    d[y] = dx+dy
                    heappush(q,[d[y],y])
        print(d[0]+1)
    k = I()
    if k == 1:
        print(1)
        quit()
    v = [[] for i in range(k)]
    for i in range(1,k):
        v[i].append([(i+1)%k,1])
        v[i].append([i*10%k,0])
    dijkstra()

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
from collections import deque

K = int(input())

while (K % 2 == 0):
    K = K // 2
while (K % 5 == 0):
    K = K // 5

if(K == 1):print("1")
else : 
    visited = [-1 for i in range(K)]
    queue = deque([])
    st = 1

    while True:
        visited[st] = 1
        queue.append(st)
        st = (10*st) % K
        if (st == 1) : break

    while queue:
        a = queue.popleft()
        if (visited[0] != -1) :break
        if (visited[(a+1) % K] == -1):
            st = (a+1) % K
            while True:
                visited[st] = visited[a] + 1
                queue.append(st)
                st = (10*st) % K
                if (st == ((a+1) % K)) : break
            if (visited[0] != -1) :break


    print(visited[0])

Solution (Python):
from collections import deque
k=int(input())
dist=[float('inf') for _ in range(k)]
dist[1]=1
q=deque()
q.append(1)
while len(q)>0:
    r=q.popleft()
    s=(r+1)%k
    if dist[r]+1<dist[s]:
        dist[s]=dist[r]+1
        q.append(s)
    t=(r*10)%k
    if dist[r]<dist[t]:
        dist[t]=dist[r]
        q.appendleft(t)
print(dist[0])

Solution (Python):
from collections import deque
v, que, k = set(), deque([(1, 1)]), input()
while que:
    n, c = que.popleft()
    if n in (0, k):
        print c
        break
    if n not in v:
        que.append((n + 1, c + 1))
        que.appendleft((n * 10 % k, c))
        v.add(n)

Solution (Python):
from collections import deque
K=int(input())
dist=[10**15 for i in range(K)]
dist[1]=1
q=deque([1])
while(len(q)>0):
    r=q.popleft()
    s=(r+1)%K
    if dist[r]+1<dist[s]:
        dist[s]=dist[r]+1
        q.append(s)
    t=(r*10)%K
    if dist[r]<dist[t]:
        dist[t]=dist[r]
        q.appendleft(t)
print(dist[0])

Solution (Python):


import collections

n = int(input())

cursor = 1
deque = collections.deque([(cursor, 0)])
visited = {cursor}

min_path = 10e10
while len(deque) > 0:
    cursor, min_path = deque.popleft()
    visited.add(cursor)
    if cursor == 0:
        break

    pone, mten = (cursor + 1) % n, (cursor * 10) % n
    if not pone in visited:
        deque.append((pone, min_path + 1))
    if not mten in visited:
        deque.appendleft((mten, min_path))

print(min_path + 1)

Solution (Python):
import heapq
K=int(input())
dist=[10**15 for i in range(K)]
dist[1]=1
q=[]
heapq.heappush(q,(0,1))
while (len(q)!=0):
    prc,src=heapq.heappop(q)
    if dist[src]<prc:
        continue
    if dist[(src+1)%K]>dist[src]+1:
        dist[(src+1)%K]=dist[src]+1
        heapq.heappush(q,(dist[(src+1)%K],(src+1)%K))
    if dist[(10*src)%K]>dist[src]:
        dist[(10*src)%K]=dist[src]
        heapq.heappush(q,(dist[(src*10)%K],(src*10)%K))
print(dist[0])

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
k = int(input())

dist = []
for i in range(k):
    if i != k - 1:
        dist.append([i, i + 1, 1])
    else:
        dist.append([i, 0, 1])

for i in range(k):
    dist.append([i, (10 * i) % k, 0])

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    
spdi = {}

d = Dijkstra(g, 1)
sp = format(d.shortest_distance(0))
print(int(sp) + 1)

Solution (Python):
from collections import deque
K = int(input())
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((10 * i) % K, 0))
    G[i].append(((i + 1) % K, 1))

dist = [float('inf')] * K
dist[1] = 1
que = deque()
que.append(1)

while que:
    n = que.pop()
    for v, c in G[n]:
        if dist[v] > dist[n] + c:
            dist[v] = dist[n] + c
            if c == 0:
                que.append(v)
            else:
                que.appendleft(v)

print(dist[0])

Solution (Python):
from collections import deque
q=deque();K=int(input());q+=[(1,1)];m={}
while len(q):
 n,s=q.pop()
 if not n in m:m[n]=s;q+=[(n*10%K,s)];q.appendleft(((n+1)%K,s+1))
print(m[0])

Solution (Python):
from collections import deque
q=deque();K=int(input());a=q.append;a((1,1));m={}
while len(q):
 n,s=q.popleft()
 if not n in m:m[n]=s;q.appendleft((n*10%K,s));a(((n+1)%K,s+1))
print(m[0])

Solution (Python):
from collections import deque
q=deque()
K=int(input())
a=q.append
a((1,1))
m={}
while len(q):
 n,s=q.popleft()
 if n in m:continue
 m[n]=s
 q.appendleft((n*10%K,s))
 a(((n+1)%K,s+1))
print(m[0])

Solution (Python):
from collections import deque
q = deque()
K = int(input())
q.append((1, 1))
m = {}
while len(q):
 n, s = q.popleft()
 if n in m:continue
 m[n] = s
 q.appendleft((n * 10 % K, s))
 q.append(((n + 1) % K, s + 1))
print(m[0])

Solution (Python):
from collections import deque

que = deque()

K = int(input())

que.append((1, 1))
visited = {}

while len(que) != 0:
    num, step = que.popleft()
    if num in visited:
        continue
    visited[num] = step
    que.appendleft((num * 10 % K, step))
    que.append(((num + 1) % K, step + 1))

print(visited[0])

Solution (Python):
from collections import deque
K = int( input())
V = [0]*K
d = deque([(1,1)])
while 1:
    w, v = d.popleft()
    if v == 0:
        ans = w
        break
    if V[v] == 1:
        continue
    V[v] = 1
    if V[ (v+1)%K] == 0:
        
        
        
        d.append((w+1 ,(v+1)%K))
    if V[ (v*10)%K] == 0:
        d.appendleft((w, (v*10)%K))
        
        
        
print(ans)

Solution (Python):
from collections import deque
K = int(input())
G = [[] for i in range(K)]

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

que = deque([[1, 1]])
dist = [float('inf')] * K

while que:
    node, cost = que.pop()
    dist[node] = min(cost, dist[node])
    for e, e_cost in G[node]:
        if dist[e] != float('inf'):
            continue

        if e_cost == 0:
            que.append([e, cost + 0])

        if e_cost == 1:
            que.appendleft([e, cost + 1])

print(dist[0])

Solution (Python):
import heapq
from collections import deque
K = int(input())
G = [[] for i in range(K)]

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


def dijkstra(x):
    d = [float('inf')] * K
    d[x] = 0
    visited = {x}

    
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


print(dijkstra(1)[0] + 1)

Solution (Python):
k = int(input())

INF = 10 ** 6

d = [INF for _ in range(k)]

d[1] = 1
temp = [[1,1]]
while 1:
    next = []
    for p, c in temp:
        if c + 1 < d[(p + 1) % k]:
            d[(p + 1) % k] = c + 1
            next.append([(p + 1) % k, c + 1])
        if c < d[(p * 10) % k]:
            d[(p * 10) % k] = c
            next.append([(p * 10) % k, c])
    if len(next) == 0:
        break
    else:
        temp = [] + next

print(d[0])

Solution (Python):
from heapq import heappush, heappop
K = int(input())
INF = float("inf")
d = [INF] * K
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((i + 1) % K, 1))
    G[i].append(((10 * i) % K, 0))

d[1] = 0
que = [(1, 0)]
while que:
    v, cost = heappop(que)
    if d[v] < cost:
        continue

    for w, c in G[v]:
        if d[w] > d[v] + c:
            d[w] = d[v] + c
            heappush(que, (w, d[w]))

print(d[0] + 1)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

k = ni()
que = deque([(1,1)])

kmod = [0]*k

while kmod[0] == 0:
    cost, idx = que.popleft()
    if kmod[idx] == 0:
        kmod[idx] = cost
        if kmod[10*idx%k] == 0:
            que.appendleft((cost, (10*idx%k)))
        if kmod[(idx+1)%k] == 0:
            que.append((cost+1, (idx+1)%k))            
        
print(kmod[0])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

k = ni()
que = deque([(1,1)])

kmod = [0]*k

while kmod[0] == 0:
    cost, idx = que.popleft()
    if kmod[idx] == 0:
        kmod[idx] = cost
        que.appendleft((cost, (10*idx%k)))
        que.append((cost+1, (idx+1)%k))            
        
print(kmod[0])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

k = ni()
que = deque([(1,1)])

kmod = [0]*k

while kmod[0] == 0:
    cost, idx = que.popleft()
    if kmod[idx] == 0:
        kmod[idx] = cost
        que.appendleft((cost, (10*idx%k)))
        que.append((cost+1, (idx+1)%k))            
        
print(kmod[0])

Solution (Python):
from collections import deque

k = int(input())

visited = [False]*(k+1)
dist = [0]*(k+1)
dist[1] = 1
que = deque([(1, 1)])

while len(que) > 0:
    cost, node = que.popleft()
    if visited[node]:
        continue
    
    visited[node] = True
    dist[node] = cost

    if not visited[10*node%k]:
        que.appendleft((cost, 10*node%k))
    if not visited[(node+1)%k]:
        que.append((cost+1, (node+1)%k))

print(dist[0])

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from heapq import heappop, heappush
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    K = int(input())
    dp = [INF] * K
    dp[1] = 1

    heap = []
    heappush(heap, (1, 1))

    while len(heap) != 0:
        k, p = heappop(heap)
        if dp[(p + 1) % K] > dp[p] + 1:
            dp[(p + 1) % K] = dp[p] + 1
            heappush(heap, (dp[p] + 1, (p + 1) % K))
        if dp[(p * 10) % K] > dp[p]:
            dp[(p * 10) % K] = dp[p]
            heappush(heap, (dp[p], (p * 10) % K))

        if dp[0] != INF:
            break

    print(dp[0])


if __name__ == '__main__':
    main()

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


class Graph(object):

    def __init__(self, K):
        self.K = K
        self.weights = {}

    def add(self, node1, node2, weight):
        if (node1, node2) in self.weights:
            self.weights[(node1, node2)] = min(self.weights[(node1, node2)], weight)
        else:
            self.weights[(node1, node2)] = weight

    def to_csr(self):
        n1, n2, w = [], [], []
        for (node1, node2), weight in self.weights.items():
            n1.append(node1)
            n2.append(node2)
            w.append(weight)
        return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))


K = int(input())
g = Graph(K)

for i in range(K):
    if i == K - 1:
        g.add(i, 0, 1)
    else:
        g.add(i, i + 1, 1)
    g.add(i, (i * 10) % K, 10**(-8))

d = dijkstra(g.to_csr(), directed=True, indices=1)
print(int(d[0]) + 1)

Solution (Python):
from collections import deque
k = int(input())
x = [50 for i in range(k)]
x[1],q = 0,deque()
q.append(1)
while q:
	n = q.pop()
	m = n	
	while 1:
		m2 = (m*10)%k
		if x[m2]>x[m]:
			x[m2],m = x[m],m2
			q.append(m)
		else: break
	if x[(n+1)%k]==50:
		x[(n+1)%k] = x[n]+1
		q.appendleft((n+1)%k)
print(x[0]+1)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

K = int(input())


lines = defaultdict(set)
for i in range(K-1):
	lines[i].add((i+1,1))
lines[K-1].add((0,1))

for s in range(K):
	t = s*10 % K
	if s != t:
		lines[s].add((t,0))

def search (s,w_0): 
	global weight
	global q

	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

s = 1
weight = [INF]*K
weight[s] = 0
q = [[0,s]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

print(weight[0]+1)

Solution (Python):
from collections import deque

def bfs(K:int) -> list:
    hasChecked = [False]*(K+1)
    cost_list = [0]*(K+1)
    cost_list[1] = 1
    
    que = deque([(cost_list[1], 1)])
    
    while que:
        cost, res = que.popleft()
        if hasChecked[res]:
            continue
        
        hasChecked[res] = True
        cost_list[res] = cost
        
        if not hasChecked[10*res%K]:
            que.appendleft((cost, 10*res%K))
            
        if not hasChecked[(res+1)%K]:
            que.append((cost+1, (res+1)%K))
            
            
    return cost_list


K = int(input())
cost_list = bfs(K)
print(cost_list[0])

Solution (Python):
K = int(input())

import heapq
def dijkstra(adj, n, start):
    dj = [10**6] * (n + 1)
    dj[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[tn] > dj[fn] + lc:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = {}
for i in range(K):
    t = adj.setdefault(i, [])
    t.append(((i + 1) % K, 1))
    t.append(((i * 10) % K, 0))

costs = dijkstra(adj, K - 1, 1)
print(costs[0] + 1)

Solution (Python):
from scipy.sparse.csgraph import dijkstra, shortest_path
from scipy.sparse import csr_matrix
K = int(input())

class Graph(object):

    def __init__(self, K):
        self.K = K
        self.weights = {}

    def add_edge(self, node1, node2, weight):
        if (node1, node2) in self.weights:
            self.weights[(node1, node2)] = min(self.weights[(node1, node2)], weight)
        else:
            self.weights[(node1, node2)] = weight

    def get_csr_matrix(self):
        n1, n2, w = [], [], []
        for (node1, node2), weight in self.weights.items():
            n1.append(node1)
            n2.append(node2)
            w.append(weight)
        return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))

g = Graph(K)

for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, (i * 10) % K, 10**(-16))

g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, ((K - 1) * 10) % K, 10**(-16))
d = dijkstra(g.get_csr_matrix(), directed=True, indices=1)
print(int(d[0]) + 1)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

K = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, (i * 10) % K, 0)
g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, ((K - 1) * 10) % K, 0)

d = Dijkstra(g, 1)
print(d.shortest_distance(0) + 1)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = deque()
    q.append((1, 0))

    vis = {}
    while q:
        u, cc = q.popleft()
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.appendleft((v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = deque()
    q.append((1, 0))

    vis = {}
    while q:
        u, cc = q.popleft()
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.appendleft((v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r+1)%K
    reached[r]=1
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
    if (reached[0]==1):
        break
print(dist[0]+1)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, deque
from bisect import bisect
from random import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60
def bfs(K):
  result = [INF] * K
  result[1] = 1
  que = deque([(1, 1)])
  while len(que) > 0:
    (d, u) = que.popleft()
    if result[u] < d:
      continue
    v0 = (10 * u) % K
    if d < result[v0]:
      result[v0] = d
      que.appendleft((d, v0))
    v1 = (u + 1) % K
    if d + 1 < result[v1]:
      result[v1] = d+1
      que.append((d+1, v1))
  return result

def solve(k):
  return bfs(k)[0]

K = read()
print(solve(K))

Solution (Python):
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r+1)%K
    reached[r]=1
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
    if (reached[0]==1):
        break
print(dist[0]+1)

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

INF = 10**9+7
A = [INF] * (K)

q = deque()
q.append(1)
A[1] = 1
while q:
    x = q.popleft()
    if A[(x*10)%K] > A[x]:
        A[(x*10)%K] = A[x]
        q.appendleft((x*10)%K)
    if A[(x+1)%K] > A[x]+1:
        A[(x+1)%K] = A[x]+1
        q.append((x+1)%K)

print(A[0])

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

d=[1000000 for x in range(K+1)]
d[1]=1

def bfs(K):
  q=deque()
  q.append(1)
  while q:
    nx=q.popleft()
    if d[(nx*10)%K]>d[nx]:
      d[(nx*10)%K]=d[nx]
      q.appendleft((nx*10)%K)
    if d[(nx+1)%K]>d[nx]+1:
      d[(nx+1)%K]=d[nx]+1
      q.append((nx+1)%K)
  return d[0]

print(bfs(K))

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

d=[1000000 for x in range(K+1)]
d[1]=0

def bfs(K):
  q=deque()
  q.append(1)
  while q:
    nx=q.popleft()
    if d[(nx*10)%K]>d[nx]:
      d[(nx*10)%K]=d[nx]
      q.appendleft((nx*10)%K)
    if d[(nx+1)%K]>d[nx]+1:
      d[(nx+1)%K]=d[nx]+1
      q.append((nx+1)%K)
  return d[0]+1

print(bfs(K))

Solution (Python):
from collections import deque

k = int(input())
q = deque()
q.append(1)
d = [float("inf")] * k
d[1] = 1
while q:
    n = q.popleft()
    l, r = (n * 10) % k, (n + 1) % k
    if d[l] > d[n]:
        d[l] = d[n]
        q.appendleft(l)
    if d[r] > d[n] + 1:
        d[r] = d[n] + 1
        q.append(r)
print(d[0])

Solution (Python):
from collections import deque

def BFS01(d,K):
    d[1] = 1
    q = deque([1])
    while q:
        n = q.popleft()
        l, r = map(lambda x: (x) % K, [n * 10, n + 1])
        if d[l] > d[n]:
            d[l] = d[n]
            q.appendleft(l)

        if d[r] > d[n] + 1:
            d[r] = d[n] + 1
            q.append(r)
    return d[0]

K = int(input())
d = [float('inf')] * K

print(BFS01(d,K))