1949: 传作业

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:14 解决:12

题目描述

某十三同学一日上学迟到,此时已经开始上早自习了,所以他只好请同学帮忙把作业传到组长那里。由于刚开学不久,某十三同学还没来得及认识所有同学,所以传作业时只好找熟悉的同学。

已知某十三与组长之间有N个他熟悉的同学,并且知道这些同学相互之间间隔的距离。因为每两个同学间传作业都需要下位,所以现在请你帮忙设计一种传作业的方案,使所有同学下位走动的总距离最小

输入

1行,为一个正整数N(N<=98),表示某十三与组长之间的他所熟悉的同学人数。

接下来N+2行,每行有N+2个正整数(integer),其中第I行的第J个数代表第I个同学与第J个同学之间的距离(第1个为某十三本人,第2到第N+1个依次为某十三熟悉的同学,第N+2个是组长)。

输出

包括一行,为一个正整数L,代表最短的总移动距离。

样例输入 复制

3
0 3 4 5 1
3 0 6 7 8
4 6 0 7 6
5 7 7 0 4
1 8 6 4 0

样例输出 复制

1