3891: 4.7 切呀切披萨——最优三角剖分

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:2 通过:1

题目描述

有一块多边形的披萨饼,上面有很多蔬菜和肉片,我们希望沿着两个不相邻的顶点切成 小三角形,并且尽可能少地切碎披萨上面的蔬菜和肉片

输入格式

输入T,表示有T组数据(1<=T<=10)

请输入顶点的个数 n (1<=n<=100)

请依次输入各顶点的连接权值n*n

输入样例 复制

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

分类标签