Problem1659--VIJOS-P1547

1659: VIJOS-P1547

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

        上届的高三在这个暑假终于要到各个城市奔向他们的大学生活了。奇怪的是学校这次异 常阔气,说要用三台车子去载他们上学。上届高三的师兄们异常兴奋……可惜的是临行的时 候,学校终于露出它“狰狞”的面孔:                 一、油费要学生自己给                 二、去第k  个城市的条件是,前k-1  个城市都要被去过                 三、同时只能有一部车子在动         师兄们也只能不断地锤胸口……         但是改乘飞机已经来不及了……         他们只好利用电脑组的优势去编一个最短路径以减少自己付的油费。 (P.S.没有人喜欢走回头路……)

Input

        第一行一个数N,代表一共要去多少个城市。         下面N-1  行,对于第I  行,有I-1  个数,表示第I  个城市分别和第I+1,I+2,I+3,……,N  的距离

Output

        一行,最短的路程

Sample Input Copy

5
1 1 1 2
33 33 33
33 33
33

Sample Output Copy

36

Source/Category