旅行商问题c++并输出最短路径，用分支限界法

旅行商问题（TSP）是一个经典的组合优化问题，其目标是在所有城市之间找到最短的回路。分支限界法是一种常用的解决TSP问题的方法。下面是一个用C++实现TSP问题并输出最短路径的代码。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int INF=1e9;
const int MAXN=15;
int n;
int w[MAXN][MAXN];
int best[MAXN];
int ans=INF;
struct node{
    int u,dis,head;//当前访问的节点，当前路径长度，已经访问的节点集合
    bool operator < (const node &rhs)const{
        return dis>rhs.dis;
    }
};
void dfs(int u,int dis,int head[]){//DFS求最优解
    if(dis>=ans)return;
    if(u==n){
        if(dis+w[head[u-1]][1]<ans){
            ans=dis+w[head[u-1]][1];
            for(int i=1;i<=n;i++)best[i]=head[i];
        }
        return;
    }
    for(int i=u;i<=n;i++){
        swap(head[u],head[i]);
        dfs(u+1,dis+w[head[u-1]][head[u]],head);
        swap(head[u],head[i]);
    }
}
void bfs(){//BFS求最优解
    priority_queue<node> q;
    q.push((node){1,0,1});
    while(!q.empty()){
        node t=q.top();
        q.pop();
        if(t.dis>=ans)break;
        if(t.u==n){
            if(t.dis+w[t.head][1]<ans){
                ans=t.dis+w[t.head][1];
                for(int i=1;i<=n;i++)best[i]=t.head;
            }
            continue;
        }
        for(int i=2;i<=n;i++){
            if((t.head&(1<<i-1))==0){
                q.push((node){i,t.dis+w[t.head][i],t.head|(1<<i-1)});
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }
    int head[MAXN];
    for(int i=1;i<=n;i++)head[i]=i;
    dfs(2,0,head);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)cout<<best[i]<<" ";
    cout<<endl;
    ans=INF;
    bfs();
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)cout<<best[i]<<" ";
    cout<<endl;
    return 0;
}

该代码中，我们先通过DFS和BFS两种方式求解TSP问题，然后输出最短路径。其中，DFS方法通过不断交换节点的位置，遍历所有可能路径，并记录最优解。BFS方法则使用优先队列，每次取出路径长度最短的节点进行拓展，并记录最优解。