Problem C. Islands Travel

最后更新于:2022-04-02 01:14:59

# Problem C. Islands Travel ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/3) ### Problem 时间限制:10000ms 单点时限:1000ms 内存限制:256MB ### 描述 There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3,Y3) ..., (XN, YN). You starts at the 1st island (X1, Y1) and your destinationis the n-th island (XN, YN). Travelling between i-th and j-th islands willcost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b}denotes the smaller value between a and b) gold coins. You want to know whatis the minimum cost to travel from the 1st island to the n-th island. ### 输入 Line 1: an integer N. Line 2~N+1: each line contains two integers Xi and Yi. For 40% data, N<=1000,0<=Xi,Yi<=100000. For 100% data, N<=100000,0<=Xi,Yi<=1000000000. ### 输出 Output the minimum cost. 样例输入 ~~~ 3 2 2 1 7 7 6 ~~~ 样例输出 ~~~ 2 ~~~
';