Решение задачи #16. Python Яндекс CodeRun, Пересадки

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Пересадки
Сложность: Лёгкая.
Статус решения: "Решено".

Условие задачи:
Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

Решение:

Python
from collections import deque, defaultdict


def build_graph(lines):
    """
    Создает граф, где вершины - линии метро, а ребра - пересадки между ними.
    
    Args:
        lines: Список линий метро. Каждая линия - множество станций.
    
    Returns:
        Граф в виде словаря, где ключи - номера линий, а значения - смежные линии.
    """
    graph = defaultdict(set)  # Граф: линия -> множество смежных линий
    
    # Проверяем пересечения между каждой парой линий
    for i in range(len(lines)):
        for j in range(i + 1, len(lines)):
            if lines[i] & lines[j]:  # Если есть общие станции
                graph[i].add(j)
                graph[j].add(i)
    
    return graph


def bfs(graph, start_lines, end_lines):
    """
    Выполняет BFS для поиска минимального числа пересадок.
    
    Args:
        graph: Граф линий метро.
        start_lines: Множество начальных линий (содержащих станцию A).
        end_lines: Множество конечных линий (содержащих станцию B).
    
    Returns:
        Минимальное число пересадок или -1, если путь недостижим.
    """
    queue = deque([(line, 0) for line in start_lines])  # Очередь: линия и число пересадок
    visited = set(start_lines)  # Множество посещенных линий
    
    while queue:
        current_line, transfers = queue.popleft()
        
        # Если достигли одной из конечных линий
        if current_line in end_lines:
            return transfers
        
        # Добавляем в очередь все смежные непосещенные линии
        for neighbor in graph[current_line]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, transfers + 1))
    
    return -1  # Если путь недостижим


def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    
    # Чтение данных
    n = int(data[0])  # Количество станций
    m = int(data[1])  # Количество линий
    
    lines = []  # Список линий метро (каждая линия - множество станций)
    for i in range(2, 2 + m):
        line_data = list(map(int, data[i].split()))
        lines.append(set(line_data[1:]))  # Пропускаем первое число (количество станций)
    
    a, b = map(int, data[2 + m].split())  # Начальная и конечная станции
    
    # Построение графа линий
    graph = build_graph(lines)
    
    # Определение начальных и конечных линий
    start_lines = {i for i, line in enumerate(lines) if a in line}
    end_lines = {i for i, line in enumerate(lines) if b in line}
    
    # Если A или B недостижимы ни на одной линии, возвращаем -1
    if not start_lines or not end_lines:
        print(-1)
        return
    
    # Поиск минимального числа пересадок
    result = bfs(graph, start_lines, end_lines)
    print(result)


if __name__ == '__main__':
    main()

Объяснение кода

Построение графа линий:
Линии метро представляем как множества станций.
Две линии соединены ребром, если у них есть общая станция (станция пересадки).

Определение начальных и конечных линий:
Находим линии, содержащие станции A и B. Начинаем BFS со всех начальных линий и завершаем, если достигаем любую из конечных линий.

BFS для линий:
Очередь содержит пары (линия, число пересадок).
Подсчитываем минимальное число пересадок при достижении конечной линии.
Вывод результата:

Если путь найден, выводим минимальное число пересадок.
Если путь недостижим, выводим −1.

Источник решения: hdhai.com