Привет, кодовые ниндзя и покорители скидок! Сегодня в наших руках не просто карта мегамолла, а карта сокровищ! Каждый магазин — это вершина в графе, коридоры между ними — рёбра. Что нам с ней делать? Обойти все магазины, потратив как можно меньше времени. Можно ходить туда-сюда, как вам угодно. Короче, берем корзинки и вперёд на охоту за сокровищами!
Шаг 1: Сколько у нас тут магазинов?
Первый вопрос на миллион: сколько у нас тут магазинов? Или, если вы в теме, сколько вершин в нашем графе?
n = len(graph)
Шаг 2: Где эта корзинка и что с ней делать?
Дальше выбираем, с какого магазина начать наш марафон. Это как выбирать, куда пойти первым на свидание: в кино или сразу в ресторан.
queue = [(mask, u, steps) for u, mask, steps in [(i, 1 << i, 0) for i in range(n)]]
Что тут происходит:
- mask — это наша шопинг-сумка. В ней мы храним, какие магазины уже обчистили (в виде битовой маски).
- u — это текущий магазин, где мы сейчас тусуем.
- steps — это наш счетчик шагов. Что-то вроде фитнес-браслета, только для мозга.
Шаг 3: Мы тут вообще кого-то ищем?
Следующий этап — это как бы наша "карта сокровищ". Мы должны знать, сколько шагов потребуется, чтобы дойти до каждого сокровища (или магазина, если уж на то пошло).
Следующий этап — это как бы наша "карта сокровищ". Мы должны знать, сколько шагов потребуется, чтобы дойти до каждого сокровища (или магазина, если уж на то пошло).
dist = {}
for mask in range(2**n):
for u in range(n):
dist[mask, u] = n * n
Для каждой комбинации "шопинг-сумка + магазин" устанавливаем максимальное расстояние. Это как если бы на каждую пару "шорты + футболка" вешать ярлык "ну очень дорого".
Финальный код с комментариями
Ой-ой, у нас тут кодик! Держитесь крепче, поехали:
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
# Считаем, сколько у нас магазинов. Чтобы знать, на что готовиться.
n = len(graph)
# Создаем очередь для нашего "пути".
# В каждом элементе будут данные в формате
# (шопинг-сумка, текущий магазин, счетчик шагов)
queue = [(mask, u, steps) for u, mask, steps in [(i, 1 << i, 0) for i in range(n)]]
# Словарик для хранения минимального числа шагов
# для каждой "шопинг-сумки" и "магазина"
dist = {}
# Заполняем этот словарик какими-то абсурдными числами.
# Ну типа, чтобы все было "очень далеко"
for mask in range(2**n):
for u in range(n):
dist[mask, u] = n * n # "Бесконечно далеко", но на самом деле нет.
# Теперь самое интересное: начинаем наш марафон!
while queue:
# Достаем из очереди текущую "шопинг-сумку",
# "магазин" и счетчик шагов
mask, u, steps = queue.pop(0)
# Если мы уже были в этом магазине с этой шопинг-сумкой
# и сделали это быстрее, чем сейчас, то пропускаем
if dist[mask, u] <= steps:
continue
# Запоминаем, что в этот раз мы быстрее
dist[mask, u] = steps
# Если шопинг-сумка полная (все магазины посещены), то ура!
# Мы все купили!
if mask == 2**n - 1:
return steps
# А если не все купили, то бежим в следующие магазины!
for v in graph[u]:
queue.append((mask | 1 << v, v, steps + 1))
Асимптотика? Что это, новый вид йогурта?
Временная сложность нашего алгоритма составляет O(2^n ⋅ n). Это как если бы вы решили обойти все магазины в молле, и каждый раз приходили бы в него с новым списком покупок.
☝️Этот тип алгоритма называется «поиск в ширину». Первоначально, эта техника была разработана для поиска оптимальных решений в настольных играх, вроде "Четыре в ряд". Кто бы мог подумать, что однажды она поможет нам оптимизировать шопинг!
Анекдот на закуску
Почему программисты так любят оптимизацию? Потому что это единственный способ сэкономить деньги без участия жены!
Итак, готовы к настоящему шопинг-марафону? Тогда вперёд, к новым вершинам и скидкам! 🚀
