Есть задача коммивояжера с сайта 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;
}
Но дело в том, что я хочу его оптимизировать. Я нашел замечательную работу по этой теме, но к сожалению не совсем понимаю как мне внедрить полученные мною знания с этой выкладки в код. Если вы мне поможете с оптимизацией, то будет очень классно! Интересуют любые ваши идеи по поводу оптимизации моего кода!