给出christofides算法的C++源码

以下是 Christofides 算法的 C++ 实现代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 5;
const int inf = 1e9;

int d[maxn][maxn], n, m;
bool vis[maxn];
int ans = 0;
vector<int> G[maxn];

int prim() {
    memset(vis, 0, sizeof(vis));
    int d[maxn];
    for (int i = 2; i <= n; i++) d[i] = inf;
    d[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        pair<int, int> t = q.top(); q.pop();
        int x = t.second;
        if (vis[x]) continue;
        vis[x] = true;
        ans += d[x];
        for (int i = 0; i < G[x].size(); i++) {
            int y = G[x][i];
            if (!vis[y] && d[y] > d[x] + ::d[x][y]) {
                d[y] = d[x] + ::d[x][y];
                q.push(make_pair(d[y], y));
            }
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x][y] = d[y][x] = min(d[x][y], z);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][j] != inf && i != j)
                G[i].push_back(j);
    for (int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end());
    printf("%d\n", prim());
    return 0;
}

该算法利用了最小生成树和欧拉回路的性质，所以在前置知识方面需要对最小生成树和欧拉回路有一定的了解。希望这个代码能够帮助到您。