中文
日本語
English
| P4281B | ||
|
Description
在二维平面上有 N 个点，从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。
求从 1 号点出发，按从 1 到 N 的顺序依次到达每个点的最小总代价。
你有 K 次机会可以跳过某个点，不允许跳过 1 号点或 N 号点
Input Format
第一行 N,K(2<=N<=500,0<=K<=N-2)
接下来 N 行每行两个数(x,y)表示第 i 个点的坐标。(-1000 <= x <= 1000, -1000 <= y <= 1000)
Output Format
输出最小代价。
Sample Input
5 2
0 0
8 3
1 1
10 -5
2 2
Sample Output
4
Hint
部分分
|
编号 |
N |
M |
|
1~3 |
<=10 |
<=10 |
|
4~9 |
<=100 |
<=100 |
|
|
|
|
|
10~15 |
<=500 |
<=500 |
Source usaco