贪心算法c++旅行商

贪心算法是一种常见的算法思想，它在求解最优化问题时，每次选择当前看起来最优的方案，最终得到的解可能不是全局最优解，但通常能得到较好的近似解。旅行商问题是一种经典的NP难问题，即给定一些城市和每对城市之间的距离，求解访问每个城市恰好一次并回到起点的最短路径。

贪心算法在求解旅行商问题时，可以按照以下步骤进行：
1. 选择一个起点
2. 找到离起点最近的未访问城市，并将其标记为已访问
3. 重复步骤2，直到所有城市均被访问
4. 将最后一个访问城市与起点相连，得到回路
5. 对回路进行优化，使得总路径最短

以下是贪心算法c++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100;
const int INF = 1e9;

int n, m;
int dist[MAXN][MAXN];
bool vis[MAXN];

int tsp(int u) {
    vis[u] = true;
    int ans = INF;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ans = min(ans, dist[u][i] + tsp(i));
        }
    }
    vis[u] = false;
    return ans == INF ? dist[u] : ans;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = dist[v][u] = w;
    }
    cout << tsp(0) << endl;
    return 0;
}