2

Есть задача коммивояжера с сайта mccme. В реализации метода ближайшего соседа нет ничего сложного, весь код я выложу на всякий случай:

    #include <iostream>
    #include <vector>
    #include <fstream>
    #include <string>
    #include <cmath>
    #include <random>
    #include <limits.h>
    using namespace std;

    long long sqr(long long x)
    {
       return x * x;
    }
    int main() {
    long long n;
    cin >> n;
    long long x[n];
    long long y[n];
    vector<int> path;
    bool used[n];
    long long dist;
    long long v0dist = LLONG_MAX;
    int v0 = 1;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        used[i] = false;
        for (int j = 0; j < i; j++) {
            dist = sqrtl(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
            if (dist < v0dist)
            {
                v0dist = dist;
                v0 = i;
            }
        }
    }
    path.push_back(v0);
    used[v0] = true;
    while (path.size() != n) {
        long long cur_el = path[path.size() - 1];
        long long LL_MAX = LLONG_MAX;
        int cur_i = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                dist = sqrtl(sqr(x[cur_el] - x[i]) + sqr(y[cur_el] - y[i]));
                if (dist < LL_MAX) {
                    LL_MAX = dist;
                    cur_i = i;
                }
            }
        }
        path.push_back(cur_i);
        used[cur_i] = true;
    }
    for (int i = 0; i < n; i++) {
        cout << path[i] + 1 << " ";
    }
    return 0;
}

Но дело в том, что я хочу его оптимизировать. Я нашел замечательную работу по этой теме, но к сожалению не совсем понимаю как мне внедрить полученные мною знания с этой выкладки в код. Если вы мне поможете с оптимизацией, то будет очень классно! Интересуют любые ваши идеи по поводу оптимизации моего кода!

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Посмотрите другие вопросы с метками или задайте свой вопрос.