Напишите программу на языке C++, которая определяет все пары городов, между которыми можно лететь ровно K

Предмет вопроса: Поиск пар городов с заданным количеством пересадок

Описание:

Для решения данной задачи можно использовать алгоритм поиска в ширину (BFS) на графе. Сначала мы создаем граф, где вершины представляют города, а ребра - наличие авиационного сообщения между городами. Затем мы запускаем алгоритм поиска в ширину из каждой вершины, чтобы найти все пути с заданным числом пересадок.

1. Считываем входные данные: количество городов N, матрицу смежности графа и желаемое количество пересадок K.
2. Создаем граф, используя матрицу смежности. Каждый элемент матрицы представляет наличие или отсутствие рейса между соответствующими городами.
3. Для каждой вершины в графе, запускаем алгоритм поиска в ширину.
4. В процессе алгоритма, поддерживаем текущее количество пересадок. Когда достигаем заданного значения K, добавляем пару городов в ответ.
5. Повторяем шаги 3 и 4 для каждой вершины графа.
6. Выводим найденные пары городов.

Например:
Входные данные:

4

0 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

2

Выходные данные:

(1, 3)

(3, 1)

Совет:
Прежде чем приступить к решению задачи, рекомендуется изучить алгоритм поиска в ширину и основы работы с графами. Это поможет вам лучше понять и реализовать алгоритм в выбранном языке программирования.

Задача на проверку:
Дана матрица смежности графа, представляющая авиационные сообщения между городами:

0 1 0 1 

1 0 1 0

0 1 0 1

1 0 1 0

Желаемое количество пересадок K = 2. Определите все возможные пары городов, между которыми можно лететь ровно K раз с пересадками.