#include<iostream>
using namespace std;
int path[100][100];//定义权值矩阵
int x[100];//存储排列编号
int ans,cur;//ans代表最短耗费,cur表示当前耗费
int track[100];//存储路径
int track2[100];//用于保存最优路径
int deep;
void Travel(int i,int n)
{
deep++;
int j;
if(i==n+1)
{
track[deep]=x[i];
if(path[x[n-1]][x[n]]!=-1&&path[x[n]][1]!=-1&&(cur+path[x[n]][1]<ans))//当到达最后一个城市,该城市和起点可达,并且和之前一个城市可达
{
ans=cur+path[x[n]][1];
for(int len=0;len<=n;len++)
{
track[n]=1;
track2[len]=track[len];//保存当前最佳路径
}
}
else
{
return;
}
}
else
{
for(j=i;j<=n;j++)
{
if(path[x[i-1]][x[j]]!=-1&&(cur+path[x[i-1]][x[j]]<ans))//当第i个城市与第j个城市之间可达,并且当前耗费加上这两个城市的耗费小于最小值
{
swap(x[i],x[j]);
cur+=path[x[i-1]][x[i]];
track[deep]=x[i];
//cout<<track[deep]<<endl;
Travel(i+1,n);
cur-=path[x[i-1]][x[i]];
swap(x[i],x[j]);
deep--;
}
}
}
}
int main()
{
int n;
cout<<"输入城市个数:"<<endl;
cin>>n;
int i,j;
cout<<"输入各个城市之间的权值矩阵:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>path[i][j];
}
}
for(i=1;i<=n; i++)
{
x[i]=i;
}
memset(track,0,sizeof(track));
ans=99999;
cur=0;
deep=0;
track[0]=1;
Travel(2,n);
if(ans==99999)
{
cout<<"不存在回路"<<endl;
}
else
{
cout<<"最小路程花费是"<<ans<<endl;
}
for(int k=0;k<=n;k++)
{
cout<<track2[k]<<" ";
if(k<n)
{
cout<<"->";
}
}
}