Description

毛大神最近在玩一个传递游戏，即有 $N$ 个人在做传递物品的游戏，这 N 个人的编号为 $1，2，3，...，N-1，N$。

游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。

即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；

毛大神想知道当物品经过所有 $N$ 个人后，整个过程的最小的代价总和是多少。

Format

Input

第一行为 $N$，表示共有 $N$ 个人；

以下为 N × N 的矩阵，第$i$行第 j 列的数为 $A[i][j]$，表示物品从编号为 i 的人传递到编号为 j 的人所花费的代价，其中 $A[i][i]=-1$（因为物品不能自己传给自己）。

Output

输出共一行一个数，为最小的代价总和。

Samples

输入数据 1
2
-1 9794
2724 -1
输出数据 1
2724
Limitation
对于 50% 的数据，$1 ≤ N ≤ 11$；

对于 100% 的数据，$1 ≤ N ≤ 16；1 ≤ A[i][j] ≤ 10000；A[i][i]=-1$。

浅浅的谈一下

第一反应肯定是搜索，然后回溯，时间复杂度乍一看可以，我们算算
……其实我也不会算（~~一个蒟蒻~~），为什么不行呢，因为有人试过了，$45$分
怎么办？
一看这题目的问法，就有一种$dp$的思路，配合这数据范围，配合这题目，状压$dp$应运而生！
什么是状压$dp$(~~其实我写过了，就copy过来了~~)
“状压DP 又叫集合动态规划。是以结合信息为状态的特殊的动态规划的问题。主要有传统集合动态规划和基于连通性状态压缩的动态规划两种。” ————百度
是不是感觉很高大尚？（~~我也觉得~~ ）
其实很简单（~~不是我说的~~）
状压dp的样子

我们回到题目：我们把每个人看成每一个点，被传递过标记成一，他就变成了这样一个样子，很想二进制枚举是吧

怎么转移？
($<<$)：左移
- 在十进制上是乘法
- 在二进制上是把整体往左挪一位，例如：$100 << 1 = 1000$
- ($>>$): 右移，和左移原理一样，把整体往右移一位
- 对于每个状态，我们枚举这个点有没有选到：如$100010$这个状态没有选第三个点

这就要用到左移和 与运算了
如果我想要表示一个$100$，表示第三个状态已被选怎么办？
很容易发现$100=1<<(3-1)$
于是我们可以总结:$想要表示第i个点被选=1<<(i-1)$
于是我们就可以用$i\&1<<(j-1)$($i$表示当前状态，$j$表示当前枚举到的点)来表示$i$状态有没有选点$j$
考虑转移?
枚举每个状态，再枚举这个状态选了那些点，再由这些点进行转移
什么意思？
例如状态$10001$，这个状态包含$1,5$这$2$个点
如果点$2$可以接到点$1$后面
那么$f[11001]=\max(\min)(f[10001]+v,f[11001])$
然后输出$f[(1<<n)-1]$全部点被选即可
这道题咋写
假如枚举到一个状态$T$,枚举这个状态有多少个存在的点，再由这个点去转移到另外没有被选过的点
等等，怎么判断$T$中，球传到哪里了？
于是，我们就要开二维数组$dp_{iT}到了第i个人，状态为T $
于是就有我们的满分代码了（注意$<<$的优先级！）

$Code$

#include<bits/stdc++.h>
//值得写解题报告! 
using namespace std;
int dp[20][1<<20],n,g[20][20];
//dp[i][T]到了第i个人，状态为T 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)dp[i][1<<(i-1)]=0;//初始 
	for(int t=1;t<1<<n;t++)//枚举状态
		 for(int i=1;i<=n;i++)
		 	if(t&(1<<i-1))//在这里面 
		 		for(int j=1;j<=n;j++)
		 			if(i!=j&&!(t&(1<<j-1)))//不在这里面
					 	dp[j][t|(1<<j-1)]=min(dp[j][t|(1<<j-1)],dp[i][t]+g[i][j]);
	int ans=1e9;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[i][(1<<n)-1]);
	cout<<ans<<endl;
	return 0;//注意"<<"优先级比"-"小 
}

题外话：普及组的题竟然会考状压，没想到