回溯法——TSP问题（解空间：排列树）
输入格式
第一行输入n，代表有n个城市。
接下来n行每行输入n个数，第i行j列的值代表i市到j市的距离，0代表城市之间不通
注意：起点和终点都为1
n<7,城市之间的距离都不超过100
输出格式
第一行输出最少的旅行费用
第二行输入旅行路径
（保证只有一条最短旅行路径）
Sample Input
4 0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
Sample Output
25
1 3 2 4 1
//#include
//using namespace std;
#includeint a[100][100],x[100],bestx[100];
int bests=11111,cs=0,n;void swap(int &a,int &b)
{int temp;temp=a;a=b;b=temp;
}void dfs(int t)
{if(t>n){//起点和终点的条件判断 if(a[x[n]][1]!=0 && cs+a[x[n]][1] 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！