旅行售货员 回溯法 pta

售货员 回溯法 pta"/>

旅行售货员 回溯法 pta

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。

输入格式:

第一行为城市数n

下面n行n列给出一个完全有向图，如 i 行 j 列表示第 i 个城市到第 j 个城市的距离。

输出格式:

一个数字，表示最短路程长度。

输入样例:

3
0 2 1
1 0 2
2 1 0

输出样例:

3

代码

#include <iostream>
#include <cstring>
using namespace std;
int max_ = 32767;   //定义一个最大值
int citynum;                //城市数
int currentcost;            //记录当前的路程
int bestcost;               //记录最小的路程(最优)
int Graph[100][100];        //图的边距记录
int x[100];                 //记录行走顺序
int bestx[100];             //记录最优行走顺序void InPut()
{int  len;     //距离cin>>citynum;memset(Graph, 0, sizeof(Graph));for(int i = 1; i <=citynum; ++i){for(int j=1;j<=citynum;++j){cin>>len;Graph[i][j]=len;}}
}//初始化
void Initilize()
{currentcost = 0;bestcost = max_;for(int i = 1; i <= citynum; ++i){x[i] = i;}
}void BackTrack(int i) //这里的i代表第i步去的城市而不是代号为i的城市
{if(i == citynum){if(currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]] < bestcost || bestcost == max_){bestcost = currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]];for(int j = 1; j <= citynum; ++j)bestx[j] = x[j];}}else{for(int j =  i; j <= citynum; ++j){if(currentcost + Graph[x[i - 1]][x[j]] < bestcost || bestcost == max_){swap(x[i], x[j]);  //这里i 和 j的位置交换了, 所以下面的是currentcost += Graph[x[i - 1]][x[i]];currentcost += Graph[x[i - 1]][x[i]];BackTrack(i + 1);   //递归进入下一个城市currentcost -= Graph[x[i - 1]][x[i]];swap(x[i], x[j]);}}}
}void OutPut()
{cout<<bestcost<<endl;
}int main()
{InPut();Initilize();BackTrack(2);OutPut();
}