编辑代码

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

int calPathLen(const vector<vector<int>>& cityMap, const vector<int>& path) {
    int len = 0;
    for (int i = 0; i < path.size() - 1; ++i) {
        len += cityMap[path[i]][path[i + 1]];
    }
    return len;
}

void tsp(const vector<vector<int>>& cityMap, int dstCity, vector<int>& curPath, int& shortestPathLen, vector<vector<int>>& shortestPaths) {
    if (curPath.size() == 0) {
        curPath.push_back(dstCity);
    }
    int curLen = calPathLen(cityMap, curPath);
    if (curLen > shortestPathLen) {
        return;
    }

    if (curPath.size() == cityMap.size()) {
        curPath.push_back(dstCity);
        int len = calPathLen(cityMap, curPath);
        if (len < shortestPathLen) {
            shortestPaths.clear();
            shortestPaths.push_back(curPath);
            shortestPathLen = len;
        } else if (len == shortestPathLen) {
            shortestPaths.push_back(curPath);
        }
        curPath.pop_back();
        return;
    }

    for (int i = 0; i < cityMap.size(); ++i) {
        if (find(curPath.begin(), curPath.end(), i) == curPath.end()) {
            curPath.push_back(i);
            tsp(cityMap, dstCity, curPath, shortestPathLen, shortestPaths);
            curPath.pop_back();
        }
    }
}

void printTspResult(int pathLen, const vector<vector<int>>& paths) {
    cout << "最短路径长度： " << pathLen << endl;
    for (const auto& path : paths) {
        cout << "路径： ";
        for (int city : path) {
            cout << city << " ";
        }
        cout << endl;
    }
}

int main() {
    // 旅行商地图1
    vector<vector<int>> cityMap1 {
        {0, 30, 6, 4},
        {30, 0, 5, 10},
        {6, 5, 0, 20},
        {4, 10, 20, 0},
    };
    int shortestPathLen1 = INT_MAX;
    vector<vector<int>> shortestPaths1;
    vector<int> curPath1;
    tsp(cityMap1, 0, curPath1, shortestPathLen1, shortestPaths1);
    printTspResult(shortestPathLen1, shortestPaths1);

    cout << "=================================================" << endl;

    // 旅行商地图2
    vector<vector<int>> cityMap2 {
        {0, 8, 5, 36},
        {6, 0, 8, 5},
        {8, 9, 0, 5},
        {7, 7, 8, 0},
    };
    int shortestPathLen2 = INT_MAX;
    vector<vector<int>> shortestPaths2;
    vector<int> curPath2;
    tsp(cityMap2, 0, curPath2, shortestPathLen2, shortestPaths2);
    printTspResult(shortestPathLen2, shortestPaths2);

    return 0;
}