Python TLE, what is wrong with my solution?


#1
import collections

class Solution:
    # @param A : integer
    # @return a strings
    def multiple(self, A):
        queue = collections.deque([1])

        result = '0'
        dest = None
        parents = {1: None}
        while queue:
            current = queue.popleft()

            if current % A == 0:
                dest = current
                break

            val1 = (current * 10) % A
            if val1 not in parents:
                parents[val1] = -current
                queue.append(val1)

            val2 = (val1 + 1) % A
            if val2 not in parents:
                parents[val2] = current
                queue.append(val2)

        # print(parents_0, parents_1)
        if dest is not None:
            tmp = []
            while dest is not None:
                dest = parents[dest]

                if dest and dest < 0:
                    dest = -dest
                    item = '0'
                else:
                    item = '1'

                tmp.append(item)
            result = ''.join(reversed(tmp))

        return result