旅游n个城市，但并不是每一条路线花费都是一样的。想把所有的城市都旅游一遍，但是花费最小。

输入格式
第一行输入一个整数n,表示有n个城市
接下来有一个n*n的矩形，表示每两个城市之间的火车花费，每两个城市之间的花费不会超过10000。

输出格式
输出一个整数，表示从1号城市把所有的景点旅游一遍并且回到1号城市的最小花费。

样例输入
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
样例输出
8

#include<iostream>
using namespace std;
int mp[10][10];
int n,ans=10000;
bool vis[10];
void dfs(int a,int cnt,int sum){//a表示当前在第a个城市，cnt表示已经去了几个城市，sum表示当前已经花费if(sum>ans){//如果花的多余上一次，剪掉 return;}if(cnt==n){//递归出口 ans=min(ans,sum+mp[a][1]);//要加上返回第一个城市的路费 return;} vis[a]=true;//标记这个城市去过 for(int i=1;i<=n;i++){//挑一个城市去 if(!vis[i]){dfs(i,cnt+1,sum+mp[a][i]);}}vis[a]=false;
}
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j];}} dfs(1,1,0);//从第一个城市出发 cout<<ans<<endl;return 0;
}