c++利用分支界限法实现旅行商问题并每行加上注释并且结果要有最短路径是什么以及最短路径的长度

以下是使用分支界限法实现旅行商问题的C++代码，每行都添加了注释：

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

const int MAXN = 20; // 最大城市数量
const int INF = 0x3f3f3f3f; // 无穷大

int n; // 城市数量
int graph[MAXN][MAXN]; // 城市间距离矩阵
int visited[MAXN] = {0}; // 标记城市是否访问过
int ans = INF; // 最短路径长度
int path[MAXN]; // 最短路径

// 定义一个结构体，用于存储搜索状态
struct Node {
    int u; // 当前所在的城市
    int depth; // 搜索深度
    int cost; // 已经走过的路径长度
    int path[MAXN]; // 已经走过的路径
};

// 定义一个比较函数，用于优先队列的排序
struct cmp {
    bool operator() (const Node& a, const Node& b) {
        return a.cost > b.cost;
    }
};

// 分支界限算法
void TSP() {
    priority_queue<Node, vector<Node>, cmp> q; // 定义一个优先队列
    Node start = {0, 1, 0, {0}}; // 起点
    q.push(start); // 将起点压入队列
    while (!q.empty()) {
        Node cur = q.top(); // 取出队头元素
        q.pop(); // 弹出队头元素
        if (cur.depth == n && graph[cur.u][0] != INF) { // 已经走过所有城市，返回起点
            cur.path[cur.depth-1] = 0; // 最后一个城市的下一个城市一定是起点
            if (cur.cost + graph[cur.u][0] < ans) { // 更新最短路径
                ans = cur.cost + graph[cur.u][0];
                for (int i = 0; i < n; i++) {
                    path[i] = cur.path[i];
                }
            }
            continue; // 继续搜索
        }
        for (int i = 0; i < n; i++) { // 枚举下一个城市
            if (!visited[i] && graph[cur.u][i] != INF) { // 如果这个城市没有被访问过，并且和当前城市相邻
                visited[i] = 1; // 标记这个城市已经被访问过
                Node next = {i, cur.depth+1, cur.cost+graph[cur.u][i], {0}}; // 创建下一个状态
                for (int j = 0; j < cur.depth-1; j++) { // 复制之前走过的路径
                    next.path[j] = cur.path[j];
                }
                next.path[cur.depth-1] = i; // 记录当前城市
                q.push(next); // 将下一个状态压入队列
                visited[i] = 0; // 还原状态
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == -1) { // 无穷大
                graph[i][j] = INF;
            }
        }
    }
    visited[0] = 1; // 起点已经被访问过
    TSP(); // 分支界限算法
    cout << "最短路径是：";
    for (int i = 0; i < n; i++) {
        cout << path[i] << " ";
    }
    cout << "0" << endl; // 最后一个城市的下一个城市一定是起点
    cout << "最短路径长度是：" << ans << endl;
    return 0;
}

以上代码实现了旅行商问题的求解，其中使用了分支界限算法。程序先读入城市间距离矩阵，然后从起点开始搜索，遍历所有可能的路径，并记录最短路径。最后输出最短路径以及最短路径的长度。

注意，如果城市间距离为无穷大，则要将其转化为一个较大的数，这里使用的是 `INF`。同时，最后一个城市的下一个城市一定是起点，因此最终输出路径时需要手动添加。