#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int num = 0;
int map[4][4] = {0,3,6,7,
5,0,2,3,
6,4,0,2,
3,7,5,0
};
vector<int> s;
void run(int x,int pre,int sum,int pass[5])
{
int i,pass_flag = 1;
//初始化副本
int pass2[5];
for(i = 0;i < 5;i++)
{
pass2[i] = pass[i];
//cout << pass2[i] << endl;
}
//当前城市做上标记
pass2[x] = map[pre][x];
//设计出口 pass中的数据都不是-1 说明到过4个城市
for(i = 0;i < 4;i++)
{
if(pass2[i] == -1)
{
pass_flag = 0;
break;
}
}
if( pass_flag )
{
//sum + 从最后一座城市返回起始城市
sum += map[x][0];
//将整个路程存放在向量s中
s.push_back(sum);
pass2[4] = map[x][0];
//输出路线
cout << "路程方案" << ++num << endl;
for(i = 1;i < 5;i++)
{
cout << pass2[i] << " " ;
}
cout << endl;
}
else
{
//加上从上一个城市到达本城市需要的路程
//sum += map[pre][x];
for( i = 0;i < 4;i++ )
{
//判断下一个城市是否已经到达过
if(pass2[i] == -1)
{
//没有达到过 便进行递归循环
run(i,x,sum+map[x][i],pass2);
//pass2[i] = 1;
}
}
}
}
int main()
{
int x = 0;
int y = 0;
int pass[5] = {-1,-1,-1,-1,-1};
//当前所在城市 走过路程 已经走过的城市
run(x,x,0,pass);
sort(s.begin(),s.end());
cout << "最长:" << *(s.end()-1) << endl;
cout << "最短:" << *s.begin() << endl;
return 0;
}