Submission #8425445

---

Source Code Expand

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)]  #q = [(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)

Submission Info

Judge Result