Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- // Класс Маршрут
- class route {
- int *r, n; // r – массив, представляющий маршрут; n – количество городов
- public:
- route(int num = 0) {
- n = num;
- r = new int[n];
- for (int i = 0; i < n; i++)
- r[i] = i;
- }
- route(const route&a) {
- n = a.n;
- r = new int[n];
- for (int i = 0; i < n; i++)
- r[i]=a.r[i];
- } // конструктор копирования
- route & operator = (const route&a) {
- if (this != &a) {
- n = a.n;
- delete []r;
- r = new int[n];
- for (int i = 0; i < n; i++)
- r[i]=a.r[i];
- }
- return *this;
- } // операция присваивания
- ~route() { if(r) delete []r; r = NULL; } // деструктор
- int route_price(int **); // вычисляет стоимость маршрута по матрице стоимости
- bool next_route(); // вычисляет следующий маршрут, используя алгоритм Дейкстры
- friend ostream & operator << (ostream&, const route&); // вывод маршрута
- };
- int route::route_price(int **arr) {
- int sum = 0;
- for (int i = 0; i < n; i++)
- sum +=arr[r[i]][r[i+1]];
- sum +=arr[r[n-1]][r[0]];
- return sum;
- }
- bool route::next_route() {
- int i = 0;
- int j;
- for (int k = n-2; k >= 1; k--)
- if(r[k]<r[k+1]) {
- i = k;
- break;
- }
- if (!(i)) return false;
- for (int k = n-1; k >= i+1; k--)
- if(r[i]<r[k]) {
- j = k;
- break;
- }
- swap(r[i],r[j]);
- for (int low = i+1, high = n-1;low<high; low++,high--)
- swap(r[low],r[high]);
- return true;
- }
- ostream & operator << (ostream& out, const route& a) {
- for (int i = 0; i < a.n; i++) {
- out<<a.r[i]<<"\t";
- }
- return out;
- }
- int main() {
- int n;
- cin>>n;
- route d(n);
- int **cost = new int*[n];
- for (int i = 0; i < n; i++) {
- cost[i] = new int[n];
- for (int j = 0; j < n; j++) {
- cin>>cost[i][j];
- }
- }
- route temp = d;
- int min = d.route_price(cost);
- cout<<temp<<"\t"<<temp.route_price(cost)<<endl;
- while(temp.next_route()) {
- cout<<temp<<"\t"<<temp.route_price(cost)<<endl;
- int tmin = temp.route_price(cost);
- if (tmin<min) {
- d = temp;
- min = tmin;
- }
- }
- cout<<min<<endl<<d;
- for (int i = 0; i < n; i++) {
- delete [] cost[i];
- }
- delete [] cost;
- return 0;
- }
- /*
- 5
- 0 3 1 3 4
- 5 0 3 2 4
- 4 4 0 2 4
- 4 8 2 0 4
- 2 8 7 1 0
- 13
- 0 1 3 2 4
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement