【回溯】旅行商问题
<center>
提交: 10 解决: 1
[提交][状态][讨论版] </center>
问题 D: 【回溯】旅行商问题
时间限制: 1 Sec 内存限制: 128 MB提交: 10 解决: 1
[提交][状态][讨论版] </center>
题目描述
旅行商问题是指一销售商从n个城市中的某一城市出发，不重复地走完其余n—1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第1个城市出发。
输入
输入包含多组测试用例。
对每个测试例，第1行有两个整数：n(4≤n≤10)和m(4≤m≤20 ) ，n是结点数，m是边数。接下来m行，描述边的关系，每行3个整数：(i，j)，length，表示结点i到结点j的长度是length。
当n＝0时，表示输入结束。
输出
对每个测试例，输出最短路径长度所经历的结点，最短的长度。
样例输入
4 6
1 2 20
1 4 4
1 3 6
2 3 5
2 4 10
3 4 15
0
样例输出
1 3 2 4
25
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m; int a1,a2,len; int cou=0; int sum=0; int graph[20][20]={0}; int yorn[20]={1,0}; int p[20]={1,0}; int path[20]={1}; int minn=99999; void backtrack(int cur){ if(cur>n){ if(sum<minn){ minn=sum; cou++; for(int i=1;i<n;i++){ path[i]=p[i]; } } }else{ if(cur==n){ if(graph[1][p[cur-1]]!=0){ sum+=graph[p[cur-1]][1]; backtrack(cur+1); sum-=graph[p[cur-1]][1]; }else{ return; } } for(int i=2;i<=n;i++){ if(sum>minn){ return; }else{ if(graph[i][p[cur-1]]!=0&&!yorn[i]){ p[cur]=i; sum+=graph[i][p[cur-1]]; yorn[i]=1; backtrack(cur+1); sum-=graph[i][p[cur-1]]; yorn[i]=0; } } } } } int main() { while(1){ scanf("%d",&n); if(n==0){ break; } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d %d %d",&a1,&a2,&len); graph[a1][a2]=len; graph[a2][a1]=len; } backtrack(1); if(cou==0){ printf("0\n"); continue; } for(int i=0;i<n;i++){ printf("%d ",path[i]); } printf("\n%d\n",minn); memset(graph,0,sizeof(graph)); memset(yorn,0,sizeof(yorn)); memset(p,0,sizeof(p)); memset(path,0,sizeof(path)); minn=99999; cou=0; sum=0; yorn[0]=1; p[0]=1; path[0]=1; } return 0; } /* 5 7 1 4 1 1 5 1 4 5 1 5 6 1 5 7 1 6 7 1 4 6 1 1 3 2 4 5 */ /************************************************************** Problem: 1373 User: zz13 Language: C++ Result: 正确 Time:0 ms Memory:1700 kb ****************************************************************/
盒马工作强度 28人发布