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
提示
两点连线的权值是其连线上的蔬菜和肉片数