1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
const int MAX = 1e5 + 1;
int X[MAX];
int Y[MAX];
int cost[MAX];
inline int min(int a, int b) {return a < b ? a : b;}
inline int abs(int a) {return a < 0 ? -a : a;}
int main()
{
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        scanf("%d %d", &X[i], &Y[i]);
        cost[i] = min(abs(X[i] - X[1]), abs(Y[i] - Y[1]));
    }
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            cost[j] = min(cost[j], cost[i] + min(abs(X[j] - X[i]), abs(Y[j] - Y[i])));
        }
    }
    printf("%d\n", cost[N]);
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX