5818: 4.7 切呀切披萨
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：20
解决：9
题目描述
有一块多边形的披萨饼，上面有很多蔬菜和肉片，我们希望沿着两个不相邻的顶点切成小三角形,并且尽可能少地切碎披萨上面的蔬菜和肉片。
输入
样例组数
t ( 0 < t < 10 )
输入顶点个数
n ( 0 < n < 100 )
输入各顶点之间的连接权值 ( 0 < a < 1000 )
a11 a12 ... a1n
a21 a22 ... a2n
...
...
an1 an2 ... ann
t ( 0 < t < 10 )
输入顶点个数
n ( 0 < n < 100 )
输入各顶点之间的连接权值 ( 0 < a < 1000 )
a11 a12 ... a1n
a21 a22 ... a2n
...
...
an1 an2 ... ann
输出
输出最优值
ans
ans
样例输入 复制
1
6
0 2 3 1 5 6
2 0 3 4 8 6
3 3 0 10 13 7
1 4 10 0 12 5
5 8 13 12 0 3
6 6 7 5 3 0样例输出 复制
54提示
两点连线的权值是其连线上的蔬菜和肉片数