206 旅行商问题

// 206 旅行商问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/14/problem/645

蜗蜗的世界里有 n个城市，城市两两之间通过高速公路连接，
从第 i个城市走到第 j个城市需要花费 ai,j的时间。

现在蜗蜗想从 1 号城市出发旅游，他想把每个城市都玩个遍，但又不想在一个城市玩两遍，玩完以后蜗蜗需要回到 1 号城市应付期末考试。
请问蜗蜗最少需要花费多少时间？

蜗蜗到了一个城市以后，一定会在这个城市游玩。蜗蜗在出发之前会先在 1 号城市游玩。
连接两个城市的高速公路不会经过其他城市。
由于路况的原因，从第 i个城市走到第 j个城市花费的时间不一定等于从第 j个城市走到第 i个城市花费的时间。

输入格式
第一行一个整数 n表示城市数目。

接下来 n行，每行 n个整数。第 i行第 j 列的整数表示 ai,j。

输出格式
一行一个整数表示答案。

样例输入
2
0 1
2 0
样例输出
3
数据范围
对于 100%的数据，保证 2≤n≤8，如果 i=j，则 ai,j=0，否则 1≤ai,j≤10000。
*/



#include <iostream>
#include <cstring>


using namespace std;

const int N = 10;
int g[N][N];

int n, k;
int vis[N], cnt,len;
int ans = 0x3f3f3f3f;

void dfs(int x,int prev) {
	vis[x] = 1; cnt++; len += g[prev][x];
	if (cnt == n && x == k) {
		ans = min(ans, len);
		len -= g[prev][x]; vis[x] = 0; cnt--; return;
	}
	else if (cnt == n) {
		len -= g[prev][x]; vis[x] = 0; cnt--; return;
	}

	for (int i = 1; i <= n; i++) {
		if (vis[i] == 1) continue;
		dfs(i, x);
	}

	len -= g[prev][x]; vis[x] = 0; cnt--; return;
}



int main()
{
	cin >> n ;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	k = 1;
	for (int i = 1; i <= n; i++) {
		if (i == k) continue;
		dfs(i,k);
	}

	cout << ans << endl;

	return 0;
}