Нашли ошибку?

До ближайшего склада

СложнаяДописатьГлава 6
Нашли ошибку?

#поиск в ширину#хеш-таблицы#несколько источниковid: ga-nearest-hub

Города соединены двусторонними дорогами. В некоторых городах есть склады. Допишите distance_to_hub(towns, roads, hubs): функция возвращает словарь «город → минимальное число дорог до ближайшего склада». Для города со складом это 0, для города, откуда склад недостижим, — -1. Пропуски помечены # TODO.

Пример

towns = ["A", "B", "C", "D", "E"]
roads = [("A", "B"), ("B", "C"), ("C", "D")]
distance_to_hub(towns, roads, {"A", "D"})
# {"A": 0, "B": 1, "C": 1, "D": 0, "E": -1}

Ограничения

Решение

from collections import deque


def distance_to_hub(towns: list[str], roads: list[tuple[str, str]], hubs: set[str]) -> dict[str, int]:
    """Для каждого города — число дорог до ближайшего склада (или -1)."""
    neighbors: dict[str, list[str]] = {town: [] for town in towns}
    for a, b in roads:
        neighbors[a].append(b)
        neighbors[b].append(a)

    dist: dict[str, int] = {}
    queue: deque[str] = deque()
    # TODO: все склады — источники: расстояние 0, в очередь

    while queue:
        town = queue.popleft()
        # TODO: обычный шаг поиска в ширину по соседям town
        pass

    return {town: dist.get(town, -1) for town in towns}

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 nearest_hub.py — тесты те же, результат покажет ✓ / ✗ и итог.