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

Конечно, я помогу вам решить эту задачу.

Перед тем как начать писать программу, давайте разберемся, как можно решить эту задачу самостоятельно.

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

Чтобы найти все пары городов, между которыми можно лететь с ровно k пересадками, мы можем использовать алгоритм обхода графа в глубину (DFS) или алгоритм обхода графа в ширину (BFS) с некоторыми модификациями.

При использовании алгоритма обхода в глубину (DFS) или в ширину (BFS) мы должны следить за количеством пересадок, которое произошло на текущем пути. Если количество пересадок равно k, то мы можем добавить пару городов в результирующий список.

Теперь, когда мы разобрались с логикой решения, давайте напишем программу на языке C++, выполняющую данные операции.

cpp

#include 

#include 



using namespace std;



// Рекурсивная функция для обхода графа и поиска пар городов

void findCities(vector>& graph, int start, int curr, int k, vector& path, vector>& result) {

    path.push_back(curr); // Добавляем текущий город в путь



    if (k == 0) { // Если количество пересадок равно k, добавляем пару городов в результат

        if (path.size() >= 2) {

            result.push_back(make_pair(path[0], curr));

        }

    }



    if (k > 0) { // Если количество пересадок больше 0, продолжаем обходить соседние города

        for (int i = 0; i < graph[curr].size(); i++) {

            if (graph[curr][i] == 1) { // Если есть прямой авиарейс между городами

                findCities(graph, start, i, k - 1, path, result);

            }

        }

    }



    path.pop_back(); // Удаляем текущий город из пути

}



int main() {

    int n; // Количество городов

    cin >> n;



    vector> graph(n, vector(n)); // Матрица смежности графа

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cin >> graph[i][j];

        }

    }



    int k; // Количество пересадок

    cin >> k;



    vector path; // Путь

    vector> result; // Результат



    // Обходим все города и вызываем функцию для поиска пар городов

    for (int i = 0; i < n; i++) {

        findCities(graph, i, i, k, path, result);

    }



    // Выводим все найденные пары городов

    for (int i = 0; i < result.size(); i++) {

        cout << result[i].first << " " << result[i].second << endl;

    }



    return 0;

}

С помощью данной программы вы сможете найти все пары городов, между которыми можно лететь ровно с k пересадками по заданной матрице смежности графа авиационных сообщений.

Пожалуйста, внимательно проверьте код перед его запуском и убедитесь, что данные вводятся правильно.