编辑代码

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

using namespace std;

// 计算两个城市之间的距离
int distance(int x1, int y1, int x2, int y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

// 贪心算法实现TSP
int greedyTSP(vector<vector<int>>& cityMap) {
    int n = cityMap.size();
    vector<bool> visited(n, false);
    vector<int> current_path;
    int current_city = 0; // 假设从第一个城市开始
    int current_distance = 0;
    int min_distance = INT_MAX;
    int next_city;

    while (visited.size() > 1) {
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                int dist = distance(cityMap[current_city][0], cityMap[current_city][1], cityMap[i][0], cityMap[i][1]);
                if (dist < min_distance) {
                    min_distance = dist;
                    next_city = i;
                }
            }
        }
        visited[next_city] = true;
        current_city = next_city;
        current_distance += min_distance;
    }

    return current_distance;
}

int main() {
    // 城市地图
    vector<vector<int>> cityMap = {
        {0, 30, 6, 4},
        {30, 0, 5, 10},
        {6, 5, 0, 20},
        {4, 10, 20, 0},
        {10, 20, 15, 30}
    };

    cout << "The shortest path length is: " << greedyTSP(cityMap) << endl;

    return 0;
}