【回溯】旅行商问题

问题 D: 【回溯】旅行商问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 1
[提交][状态][讨论版]

题目描述

旅行商问题是指一销售商从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
****************************************************************/