Discrete Mathematics. Laboratory work №8.

gistfile1.cpp

#include <iostream>
#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <iomanip>
#include <algorithm>

using namespace std;

inline float cartesianDistance(pair< float, float > a, pair< float, float> b) {
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

void solve(vector< vector< float > >& g, vector< bool >& used, vector< int >& path, float& value, int start, int v) {
    used[v] = true;
    path.push_back(v + 1);

    if(path.size() == g.size()) {
        value += g[v][start];
        path.push_back(start + 1);
        return;
    }

    int min_index = -1;
    for(int i = 0; i < g.size(); i++)
        if((v != i && !used[i]) && (min_index < 0 || g[v][i] < g[v][min_index]))
            min_index = i;

    value += g[v][min_index];

    solve(g, used, path, value, start, min_index);

}

int main(void) {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;

    vector< pair<float, float> > points;
    for(int i = 0; i < n; i++) {
        float x, y;
        cin >> x >> y;
        points.push_back(make_pair(x, y));
    }

    // build graph
    vector< vector< float > > g(n, vector< float > (n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            g[i][j] = cartesianDistance(points[i], points[j]);
        }
    }

    cout << "matrix: " << endl;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << fixed << setw(5) << setprecision(2) << g[i][j] << " ";
        }
        cout << endl;
    }

    vector< bool > used(n, false);
    vector< int > rpath, path;
    float rvalue = 9999999.0f, value = 0.0f;
    for(int i = 0; i < n; i++) {
        solve(g, used, path, value, i, i);
        if(value < rvalue) {
            rpath = path;
            rvalue = value;
        }
        path.clear();
        used.assign(n, false);
        value = 0.0f;
    }

    cout << "answer: " << setprecision(2) << rvalue << endl;
    cout << "path:" << endl;
    for(auto x: rpath)
        cout << x << " ";
    cout << endl;
    return 0;
}