解决旅行商问题的c++代码

旅行商问题是一个NP难问题，目前没有能够高效解决所有情况的算法。但是可以使用近似算法来求解。这里提供一个使用贪心算法来近似解决旅行商问题的C++代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 20;  // 最大城市数
int n;                // 城市数
double g[MAXN][MAXN]; // 城市间距离
bool vis[MAXN];       // 标记城市是否已访问

// 欧几里得距离
double dist(int i, int j) {
    return sqrt(pow((i - j), 2) + pow((i - j), 2));
}

// TSP贪心算法
double TSP() {
    double ans = 0;
    fill(vis, vis + n, false);
    vis[0] = true;
    int cur = 0; // 当前所在城市
    for (int i = 1; i < n; ++i) {
        int next = -1;
        double minDist = 1e9;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && g[cur][j] < minDist) {
                next = j;
                minDist = g[cur][j];
            }
        }
        if (next == -1) {
            return ans;
        }
        vis[next] = true;
        ans += minDist;
        cur = next;
    }
    ans += g[cur][0];
    return ans;
}

int main() {
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }
    // 计算城市间距离
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = dist(x[i], x[j]) + dist(y[i], y[j]);
        }
    }
    printf("%.2lf\n", TSP());
    return 0;
}

以上代码使用欧几里得距离计算城市间距离，然后使用贪心算法求解TSP问题。