针叶林切题

题目描述:

真实的信徒，从不做虚伪的掩饰。

针叶林在切WZOJ！

现在针叶林有n道题要切，由于针叶林水平很高，每次切题花费的时间都可以忽略不计。

但是针叶林在两道题之间切换需要一个时间，这让针叶林很不爽，所以她想写一个程序帮她规划一个时间最小的切题顺序。

伟大的针叶林在1ms之内就解决了这个问题，现在她想用这个问题考考你。

输入格式:

第一行一个数n，表示题目数。

接下来n行，每行n个数，表示一个矩阵a，其中a[i][j]表示针叶林从第i题切换至第j题所需的时间。

数据保证a[i][i]=0。

输出格式:

一个数，表示最小时间。

数据范围:

对50%的数据，1≤n≤8。

对100%的数据，1≤n≤18，0≤a[i][j]≤10000。

样例输入:

3
0 2 3
2 0 3
3 2 0

样例输出:

4

提示:

注意针叶林打开第1道题是不需要时间的。

注意a[i][j]不一定等于a[j][i]。

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

---

来源: zhenyelin