3826: 城市路径【递推】
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：68
解决：14
题目描述
地图上有n个城市，一只奶牛要从1号城市开始依次经过这些城市，最终到达n号城市。但是这只奶牛觉得这样太无聊了，所以它决定跳过其中的一个城市（但是不能跳过1号和n号城市），使得它从1号城市开始，到达n号城市所经过的总距离最小。假设每一个城市i都有一个坐标（xi，yi），从（x1，y1）的城市1到（x2，y2）的城市2之间的距离为|x1-x2|+|y1-y2|。
输入
第1行1个正整数n，表示城市个数。
接下来的n行，每行2个数xi和yi，表示城市i的坐标。
输出
一行一个数，使得它从1号城市开始，跳过某一个城市，到达n号城市所经过的最小总距离。
样例输入 复制
4
0 0
8 3
11 -1
10 0样例输出 复制
14提示
【样例说明】跳过2号城市
【数据规模】
对于40%的数据满足：n<=1000.
对于100%的数据满足：3<=n<=100000,-1000<=xi,yi<=1000.