[ create a new paste ] login | about

Link: http://codepad.org/XHvPTRAa    [ raw code | output | fork ]

C++, pasted on Nov 8:
#include <iostream>
#include <iomanip>
//#include <windows.h>
 
using namespace std;
 
//Функция проверки, можно ли перейти в данный узел
bool check(int key, int *mas, int kol) {
    for (int j = 0; j < kol; j++)
        if (mas[j] == key)   //Если переход в этот узел уже был
            return false;
    return true;
}
 
int main() {
   // SetConsoleCP(1251);
   // SetConsoleOutputCP(1251);
 
    int kol;
    do  //Ввод кол-ва узлов сети
    {
        cout << "Введите количество узлов(2-10) --> ";
        cin >> kol;
    } while (kol < 2 || kol > 10);
    //Создание матрицы смежности
    int **arr = new int *[kol];
    for (int i = 0; i < kol; i++)
        arr[i] = new int[kol];
 
    int rasst;
    for (int i = 0; i < kol; i++) {
        for (int j = i; j < kol; j++) {
            if (i == j)  /*Если одинаковые точки - заполняем нулями, чтобы получилась главная диагональ нулей */
            {
                arr[i][j] = 0;
                continue;
            }
            do  /*Ввод расстояния между узлами для заполнения матрицы смежности */
            {
                cout << "Введите расстояние от узла " << i << " до узла " << j << " --> ";
                cin >> rasst;
            } while (rasst < 1);
            arr[i][j] = arr[j][i] = rasst;
        }
    }
    //Вывод матрицы смежности
    cout << endl << "Матрица смежности: ";
    for (int i = 0; i < kol; i++) {
        cout << endl;
        for (int j = 0; j < kol; j++)
            cout << setw(5) << arr[i][j];
    }
     int *route = new int[kol];   /* Маршрут (массив узлов сети, в которых мы побывали в порядке посещения) */
 
    cout << endl;
    char ans;
    int start;
    do {
        for (int i = 0; i < kol; i++)    //Заполняем массив -1
            route[i] = -1;
        do  //Ввод стартового узла
        {
            cout << "Введите стартовый узел --> ";
            cin >> start;
        } while (start < 0 || start > kol - 1);
 
        route[0] = start;
        int now = start;
        int path = 0;                   // длина уже пройденного пути
        cout << "\nМаршрут:" << endl;
        for (int i = 1; i < kol; i++) {     /* i - индекс по маршруту и количество переходов, не считая возврата в стартовый узел */
            int min = INT_MAX; int min_town;
            for (int j = 0; j < kol; j++) {
                if (check(j, route, kol) && arr[now][j] < min && arr[now][j] > 0) {  //Нахождение минимума
                    min = arr[now][j];    // запомнили текущий минимум
                    min_town = j; // запомнили номер узла для тек.мин.
                }
            }
            /* здесь min - действительный минимум и min_town - номер узла с минимальным расстоянием от текущего */
            path += min;            // добавляем к общему пути
            route[i] = min_town;    // добавляем узел в маршрут
            cout << setw(2) << now << " -> " << setw(2) << route[i] << "   (расстояние " << min << ", путь " << path << ")" << endl;
            now = route[i];
        }
        // обрабатываем возврат в стартовый узел
        path += arr[start][now];
        cout << setw(2) << now << " -> " << setw(2) << start << "   (расстояние " << arr[start][now] << ", путь " << path << ")" << endl;
        cout << "Общая длина пройденного пути: " << path << endl;
 
        cout << endl << "Желаете продолжить поиск путей?(+, если да) --> ";
        cin >> ans;
 
    } while (ans == '+');
 
    delete[] route; //Удаление массива пройденных узлов
 
    //Удаление матрицы смежности
    for (int i = 0; i < kol; i++)
        delete[] arr[i];
    delete[] arr;
 
    system("pause");
    return 0;}


Output:
1
2
3
cc1plus: warnings being treated as errors
In function 'int main()':
Line 72: warning: 'min_town' may be used uninitialized in this function


Create a new paste based on this one


Comments: