702 旅行商

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

/*

http://oj.daimayuan.top/course/5/problem/249

蜗蜗的世界里有 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≤18
，如果 i=j，则 ai,j=0，否则 1≤ai,j≤10000。


3
0 1 2
1 0 2
1 2 0

3
0 3 2
2 0 3
3 2 0


*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int path[N][N];
int dp[1 << N][N];
int n;




int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> path[i][j];
		}
	}
	memset(dp, 0x3f, sizeof dp);
	dp[1][1] = 0;
	int ans = 0x3f3f3f3f;
	for (int st = 0; st < 1 << n; st++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;
				if ((st & (1 << (i-1)) ) && ( (st & (1 << (j-1))) == 0)) {
					dp[st | (1 << (j-1))][j] = min(dp[st | (1 << (j-1))][j], dp[st][i] + path[i][j]);
				}
				if ( j!=1 && ((st | (1 << (j-1))) == (1 << n) - 1) ) {
					ans = min(ans, dp[st | (1 << (j-1))][j] + path[j][1]);
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}