问题描述
某售货员要到若干城市去推销商品,已知各城市之间的路程(旅费),他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(总旅费)最小。
输入
输入第一行为一个整数n,表示图的顶点数
输入第二行为一个整数k,表示图的边数
输入第3到k+3-1行表示边的信息,每一行三个数,分别表示顶点i,顶点j,i到j的路径长度a[i][j]
4
6
1 2 30
1 3 6
1 4 4
2 3 5
2 4 10
3 4 20
输出
输出有两行
第一行为最优值,表示旅行商的最短路径长度
第二行为最优解,为旅行商的顶点遍历序列
25
1 3 2 4 1
int n;//城市的个数
double dist[N][N];//保存两城之间的距离,即有权值得边,得邻接矩阵
//path :已搜索得路径
//visited:对各城市访问与否
//currentLength:所有已检索路径得长度
//在访问得所有城市路径中,返回最短路径
double shortestPath(vector<int>&path,vector<bool>&visited,double currentLength){
//初始化部分
if(path.size() == n)
return currentLength += dist[path[0]][path.back()];//还有加上把最后一个城市与第一个城市之间的距离
double ret = INF;
//常识所有可能得下一个访问得城市。
for(int next = 0;next <n;++next){
if(visited[next])continue;
int here = path.back();
path.push_back(next);
visited[next] = true;
//利用递归完成剩余的路径的检索,并得到最短路径的长度。
double cand = shortestPath(path,visited,currentLength+dist[here][next]);
ret += min(ret,cand);
visited[next] = false;
path.pop_back();
}
return ret;
}