传递游戏

题目描述:

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

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

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

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

输入格式:

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

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

输出格式:

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

样例输入:

2
-1 9794
2724 -1

样例输出:

2724

提示:

对于50%的数据： 1≤N≤11；

对于100%的数据：1≤N≤16；1≤A[i][j]≤10,000；A[i][i]=-1

时间限制: 1000ms
空间限制: 256MB

---