Мобильная версияЯ решаю проблему с хакерским рейтингом: кратчайший доступ к BFS
подсказка о проблеме и образец ввода
Мое решение работает для всех случаев, кроме 1. Кажется, возникает ошибка во время выполнения для очень больших размеров входных данных. Я оптимизировал все, что мог, например, используя алгоритм линейного бега. Единственное, что, как я думаю, может испортить мою эффективность использования времени, это, возможно, раздел обработки ввода, где я помещаю все свои данные в hashMap. Однако это всего лишь O(edges), то есть размер заданного массива ребер.
Любые подсказки были бы полезны. Завтра собеседование по программированию
Изображение ошибки выполнения
какой результат мне нужен
def bfs(n, m, ребра, s): # Напишите здесь свой код # создаем хэш-карту, содержащую вершины adj resList = [-1] * n # обработка ввода adjMap = {} для края в краях: если край[0] отсутствует в adjMap: новыйSet = установить() adjMap[edge[0]] = новыйSet если край[1] отсутствует в adjMap: новыйSet = установить() adjMap[edge[1]] = новыйSet adjMap[edge[0]].add(край[1]) adjMap[edge[1]].add(край[0]) очередь = дек() valQueue = дек() посетил = установить() # инициализировать очередь очередь.append(ы) valQueue.append(0) resList = 0 посетил.добавить(я) пока очередь: # dequeueNode = очередь.pop(0) dequeueNode = очередь.popleft() # dequeueNodeVal = valQueue.pop(0) dequeueNodeVal = valQueue.popleft() adjSet = adjMap[dequeueNode] для adj в adjSet: если прил не посещен: посетил.добавить(прил.) очередь.добавление(прилаг) valQueue.append(dequeueNodeVal + 6) resList[adj - 1] = dequeueNodeVal + 6 resList.remove(0) вернуть список результатов Изначально моя очередь представляла собой просто список
очередь = [] очередь.append(бла) очередь.поп(0) Как и в случае с началом списка, который, как я знаю, неэффективен, поскольку требует переиндексации. В любом случае я изменил его на модуль deque из коллекций, поскольку знаю, что это более эффективно. В остальном я совсем застрял.
