Сталкер (не проходит по памяти)

@DarkShaddow · Регистрация: 03.10.2020

Студворк — интернет-сервис помощи студентам

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.

Формат ввода
В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.
В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri - количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + ... + rK ≤ 300 000).
Формат выходных данных

В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.

Пример.
Ввод:
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12

Вывод:
3

Мой алгоритм такой: каждую карту разбиваю на компоненты связности и далее строю граф, где вершиной является номер компонента связности. И далее иду по этому графу обходом в ширину. Так же учитываю, что начало и конец могут быть сразу в нескольких компонентах связности.
Мой алгоритм вроде выдает верный ответ, но по памяти все плохо. Что я делаю не так?
Мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def solution():
    def dfs(vert):
        neighbour_vert = graf[vert]
        graf[vert] = False
        for now_vert in neighbour_vert:
            if graf[now_vert] != False:
                dfs(now_vert)
        if len(intersection_con[vert]) >= 1:
            for con_two in intersection_con[vert]:
                graf_con[con_two].append(count_con)
                graf_con[count_con].append(con_two)
        intersection_con[vert].append(count_con)
 
    houses, maps = map(int, input().split())
    intersection_con = [[] for _ in range(houses+1)]    # для каждого дома записываем с какими связностями он пересекается
    count_con = 0
    graf_con = []   # граф связностей
    for _ in range(maps):
        # roads = int(data[i])
        roads = int(input())
        graf = {}
        for _ in range(roads):
            # house_one, house_two = map(int, data[i].split())
            house_one, house_two = map(int, input().split())
            try:
                graf[house_one].append(house_two)
            except KeyError:
                graf[house_one] = [house_two]
            try:
                graf[house_two].append(house_one)
            except KeyError:
                graf[house_two] = [house_one]
        for vert in graf:
            if graf[vert] != False:
                graf_con.append([])
                dfs(vert)   # проверяем связность
                count_con += 1
 
    graf_con = [set(intersection) for intersection in graf_con]     # чтобы ребра не повторялись
    start_cons = intersection_con[1]
    end_cons = intersection_con[houses]
    intersection_con = []
    queue = [start_con for start_con in start_cons]
    distance = [-1]*(count_con)
    for st_con in queue:
        distance[st_con] = 1    # за первую загруженную карту надо заплатить
 
    for con in queue:
        for neighbour_con in graf_con[con]:
            if distance[neighbour_con] == -1:
                distance[neighbour_con] = distance[con] + 1
                queue.append(neighbour_con)
 
    ans = -1   # минимум переключений карт
    for end_con in end_cons:
        if (distance[end_con] < ans and distance[end_con] != -1) or ans == -1:
            ans = distance[end_con]
    print(ans)
solution()

@eaa · 13.03.2023, 08:57

DarkShaddow, dfs = bfs ?

@DarkShaddow · 13.03.2023, 09:19 **[ТС]**

eaa, да, ошибся

@eaa · 13.03.2023, 09:21

DarkShaddow, тут наверное нужно брать дек из модуля collections.

@DarkShaddow · 13.03.2023, 09:38 **[ТС]**

eaa, использовать дек вместо очереди? Думаете из-за очереди памяти много тратиться?

@Red white socks · 13.03.2023, 12:05

А какие ограничения на память? Питон тратит 28 байт на целое число, оценочно придется потратить порядка 100МБ (2к х 2к х 28) + что-то на служебные расходы, грубо говоря 120-150МБ. Возможно стоит воспользоваться менее расточительным ЯП.

@DarkShaddow · 13.03.2023, 12:11 **[ТС]**

256 МБ

@DarkShaddow · 13.03.2023, 12:13 **[ТС]**

Сообщение от Red white socks

Возможно стоит воспользоваться менее расточительным ЯП.

Я тоже так подумал, поэтому переписал все на С++, но и там были проблемы с памятью. Похоже дело в моём алгоритме, но я не могу понять, где я допустил ошибку, чтобы так много памяти ело.

@Red white socks · 13.03.2023, 13:05

Я тут понял, что чересчур оптимистично память посчитал. Давайте еще раз.
Граф в котором ищем путь:
Вершины - пара (город, карта)
Ребра - с весом 1: (город_i, карта_j) - (город_i, карта_к), т.е. загрузка новой карты
и с весом 0: (город_i, карта_j) - (город_к, карта_j), т.е. перемещение по карте.
Ищем поиском в ширину. Что по памяти потребуется?
Множество посещенных вершин + список(очередь) текущих вершин. 200МБ, да? Ну и на хранение графа примерно столько же. Небольшой перебор намечается, придется вершину кодировать одним числом. Впритык, но вроде укладываемся. С С++ вообще не должно быть проблем

@DarkShaddow · 13.03.2023, 13:30 **[ТС]**

Red white socks, можете, пожалуйста, алгоритм немного поподробнее описать? В особенности, как строить такой граф.

Добавлено через 4 минуты
Red white socks, Я так понимаю надо все вершины одной карты связать с номером карты. Так же одна вершина может быть связана с несколькими картами и дороги оставить (то есть вершина может быть связана и с другими вершинами?). Вершины, обозначающие карты надо как-то обозначить, чтобы те от обычных вершин отличались (как?) и далее при проходе через такую вершину прибавлять 1? То есть по итогу мы получаем граф 1, 0? Если, да, то как его обойти? Через алгоритм Дейкстры или немного изменить bfs (идти в глубину пока не наткнемся на вершину с картой)?
Я верно понял алгоритм?

@eaa · 13.03.2023, 13:32

я тут с утра начинал решать... но пока нет времени...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque
 
n, k = map(int, input().split())
graph = {}
maps = {i: set() for i in range(1, n + 1)}
for i in range(1, k + 1):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        maps[i].add(x)
        maps[i].add(y)
        key1, key2 = (i, x), (i, y)
        graph.setdefault(key1, set()).add(key2)
        graph.setdefault(key2, set()).add(key1)
        
 
print(graph)

Добавлено через 1 минуту
DarkShaddow, 0-1 bfs погугли

@DarkShaddow · 13.03.2023, 13:33 **[ТС]**

eaa, только я так и не совсем понял, где использовать дек. Вместо очереди?

@eaa · 13.03.2023, 13:34

https://habr.com/ru/post/200560/

@DarkShaddow · 13.03.2023, 13:37 **[ТС]**

Сообщение от eaa

0-1 bfs погугли

А ведь графы 1, 0 можно же и через алгоритм Дейкстры решить? Ведь по факту это обычный взвешенный граф

@eaa · 13.03.2023, 13:40

DarkShaddow, Дейкстрой медленнее будет.

Добавлено через 46 секунд
и я не уверен, что на питоне эта задача вообще проходит.

@DarkShaddow · 13.03.2023, 13:53 **[ТС]**

eaa,

Сообщение от eaa

Дейкстрой медленнее будет

понял

Сообщение от eaa

не уверен, что на питоне эта задача вообще проходит

Её можно на питоне решить. По крайне мере нашлись такие люди.

Добавлено через 2 минуты
+ у меня есть возможноть отправить решение через PyPy (он обычно быстрей стандартного питона, но памяти больше ест)

@rRczZZ · 13.03.2023, 13:56

DarkShaddow, ну так у тебя, напимер, на таком графе:

Кликните здесь для просмотра всего текста

уже получается 6 компонент связности и ты хранишь в graf_con 30 рёбер (хотя можно 15ю обойтись, т.к. у всех вес один рубль), а если если через дополнительную вершину идти, то получится 12 ребер (половина с весом в один рубль, половина - 0 рублей). В общем случае получатся по рёбрам n·(n-1)/2 против 2n (где n - число компонент связности).

@DarkShaddow · 13.03.2023, 14:03 **[ТС]**

rRczZZ,
То есть все же лучше переделать граф (соединить вершины с картами) и считать через 0-1 bfs. Верно?

@Red white socks · 13.03.2023, 14:31

Сообщение от DarkShaddow

Я верно понял алгоритм?

Алгоритм примерно такой:
Нумеруем города и карты.
Потребуется множество посещенных вершин (город, карта) и две очереди со списком текущих вершин.
Для удобства пусть также у нас есть функция получения связных вершин (не путать с соседними) к данной по данной карте.
Шаг 0. Инициализируем счетчик шагов со значением 1. Добавляем в первую очередь стартовый город (здание) по всем картам (далее все занесения в очередь проводятся с проверкой на посещение и занесением во множество посещенных вершин).
Шаг 1а. По каждой вершине первой очереди добавляем во вторую очередь связные к ней вершины (которые не посещались).
Шаг 1б. Увеличиваем счетчик шагов на 1. По каждой вершине из второй очереди и добавляем в первую с тем же номером города, но с другой карты (если нет в списке посещения). Когда очередь 2 стала пуста - переходим к шагу 1а.
Выход из цикла - посещение конечного города на любой карте. В счетчике шагов будет ответ.

@DarkShaddow · 13.03.2023, 14:40 **[ТС]**

Только, как я понимаю вы имели ввиду здания, а не города (в условиях задачи именно здания)?

Новые блоги и статьи Все статьи Все блоги /
Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.03.2023, 08:57
	DarkShaddow, dfs = bfs ? 0

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 09:19 [ТС]
	eaa, да, ошибся 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.03.2023, 09:21
	DarkShaddow, тут наверное нужно брать дек из модуля collections. 1

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 09:38 [ТС]
	eaa, использовать дек вместо очереди? Думаете из-за очереди памяти много тратиться? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	13.03.2023, 12:05
	А какие ограничения на память? Питон тратит 28 байт на целое число, оценочно придется потратить порядка 100МБ (2к х 2к х 28) + что-то на служебные расходы, грубо говоря 120-150МБ. Возможно стоит воспользоваться менее расточительным ЯП. 0

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 12:11 [ТС]
	256 МБ Миниатюры 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	13.03.2023, 13:05
	Я тут понял, что чересчур оптимистично память посчитал. Давайте еще раз. Граф в котором ищем путь: Вершины - пара (город, карта) Ребра - с весом 1: (город_i, карта_j) - (город_i, карта_к), т.е. загрузка новой карты и с весом 0: (город_i, карта_j) - (город_к, карта_j), т.е. перемещение по карте. Ищем поиском в ширину. Что по памяти потребуется? Множество посещенных вершин + список(очередь) текущих вершин. 200МБ, да? Ну и на хранение графа примерно столько же. Небольшой перебор намечается, придется вершину кодировать одним числом. Впритык, но вроде укладываемся. С С++ вообще не должно быть проблем 1

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 13:30 [ТС]
	Red white socks, можете, пожалуйста, алгоритм немного поподробнее описать? В особенности, как строить такой граф. Добавлено через 4 минуты Red white socks, Я так понимаю надо все вершины одной карты связать с номером карты. Так же одна вершина может быть связана с несколькими картами и дороги оставить (то есть вершина может быть связана и с другими вершинами?). Вершины, обозначающие карты надо как-то обозначить, чтобы те от обычных вершин отличались (как?) и далее при проходе через такую вершину прибавлять 1? То есть по итогу мы получаем граф 1, 0? Если, да, то как его обойти? Через алгоритм Дейкстры или немного изменить bfs (идти в глубину пока не наткнемся на вершину с картой)? Я верно понял алгоритм? 0

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 13:33 [ТС]
	eaa, только я так и не совсем понял, где использовать дек. Вместо очереди? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.03.2023, 13:34
	https://habr.com/ru/post/200560/ 2

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.03.2023, 13:40
	DarkShaddow, Дейкстрой медленнее будет. Добавлено через 46 секунд и я не уверен, что на питоне эта задача вообще проходит. 2

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 14:03 [ТС]
	rRczZZ, То есть все же лучше переделать граф (соединить вершины с картами) и считать через 0-1 bfs. Верно? 0

@DarkShaddow 7 / 7 / 0 Регистрация: 03.10.2020 Сообщений: 164
	13.03.2023, 14:40 [ТС]
	Только, как я понимаю вы имели ввиду здания, а не города (в условиях задачи именно здания)? 0