题目：
假设A、B、C、D、E各城市间路费如下表所列，左起一列是起点，上面一行是终点，即从A到B的旅费是7，从B到A时6。某人想从一个城市出发游览各城市一遍，在回到出发地，而所用的旅费最少。请编写一程序，求出从各地出发回到出
发地的所有最佳路线。
A B C D E
A 0 7 3 10 15
B 6 0 5 13 12
C 4 8 0 5 10
D 9 11 6 0 11
E 17 14 9 8 0
代码：
#include <iostream>
using namespace std;
#define MAX 1000
const int N=5;
char City[N]={'A','B','C','D','E'};
int map[N][N]={{MAX,7,3,10,15},{6,MAX,5,13,12},{4,8,MAX,5,10},{9,11,6,MAX,11},{17,14,9,8,MAX}};
int visited[N]; //该城市是否访问
int visit[N]; //记录第i次去的城市
int road[N]; //路线
int cost; //费用
int start;//起点城市
int c;
void read(){
cout<<"城市旅游费用如下："<<endl<<" ";
for(int i=0;i<N;i++) printf("%8c",City[i]);
cout<<endl;
for(int i=0;i<N;i++){
cout<<City[i];
for(int j=0;j<N;j++)
printf("%8d",map[i][j]);
cout<<endl;
}
cout<<endl;
}
//输出行程
void print(){
cout<<"从城市"<<City[start]<<"出发的最短行程为：";
for(int j=0;j<N;j++)
cout<<City[road[j]]<<"->";
cout<<City[start]<<endl;
cout<<"费用为："<<cost<<endl<<endl;
}
//初始化
void init(){
cost=MAX;
c=0;
for(int i=0;i<N;i++){
visited[i]=0;
visit[i]=-1;
}
}
void Travel(int n){
if(n==N){ //全部城市旅游完
if(c+map[visit[n-1]][start]<cost){ //返回起点且总费用最少
for(int j=0; j<n; j++) road[j]=visit[j];
cost=c+map[visit[n-1]][start];
return;
}
}
else{
for(int i=0;i<N;i++){
if(visited[i]==0&&c+map[visit[n-1]][i]<cost) {
visit[n]=i;
visited[visit[n]]=1;
c+=map[visit[n-1]][i];
Travel(n+1);//搜索下一个城市
c-=map[visit[n-1]][i]; //返回，删除节点
visited[visit[n]]=0;
}
}
}
}
int main(){
read();
for(int i=0;i<N;i++){
init();
start=i;
visit[0]=i;//设置出发点
visited[start]=1;
Travel(1);
print();
}
return 0;
}
