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

Станислав

61

Хорошо, для решения этой задачи на языке C++ можно использовать алгоритм обхода графа в глубину (DFS). Вот подробный код программы:

cpp

#include 

#include 



using namespace std;



const int MAXN = 50;



int n, k;

int graph[MAXN][MAXN];

vector path;



void printPaths(int city, int depth) {

    path.push_back(city);



    if (depth == k) {

        for (int i = 0; i < path.size() - 1; i++) {

            cout << path[i] << " -> ";

        }

        cout << path[path.size() - 1] << endl;

    } else {

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

            if (graph[city][i] == 1) {

                printPaths(i, depth + 1);

            }

        }

    }



    path.pop_back();

}



int main() {

    cin >> n;

    

    // Считываем матрицу смежности

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

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

            cin >> graph[i][j];

        }

    }



    cin >> k;



    // Поиск всех возможных путей

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

        printPaths(i, 0);

    }



    return 0;

}

Эта программа сначала считывает количество городов `n`. Затем она считывает матрицу смежности `graph`, где `graph[i][j]` равно 1, если есть прямой авиарейс между городами `i` и `j`, и 0 в противном случае.

Далее программа считывает желаемое количество пересадок `k`.

Алгоритм DFS рекурсивно обходит граф, начиная с каждого города. При достижении глубины `k` программа выводит текущий путь. Путь хранится в векторе `path`. Если глубина `k` не достигнута, программа рекурсивно вызывает `printPaths` для каждого города, с которым есть прямой авиарейс из текущего города.

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

Например, для входных данных:

4

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

2

Результатом выполнения программы будет:

0 -> 1 -> 3

1 -> 0 -> 3

3 -> 1 -> 0

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