#873. 海底高铁
海底高铁
题目描述
该铁路经过 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 段铁路连接了城市 和城市 $i+1(1\leq i
输入格式
第一行两个整数,。
接下来一行, 个数字,表示 。
接下来 行,表示第 段铁路的 。
输出格式
一个整数,表示最少花费。
样例
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10
6394
题目来源:洛谷 P3406