平面旅行

D e s c r i p t i o n Description Description

牛牛最近在玩某款游戏，其地图可以看成一个平面直角坐标系。

地图上存在n个小镇，小镇从1到n编号。第i个小镇的坐标为 ( x i , y i ) (x_i,y_i) (xi​,yi​)。定义两个小镇的距离为曼哈顿距离，比如小镇i到小镇j的距离为 ∣ x i − x j ∣ + ∣ y i − y j ∣ |x_i-x_j|+|y_i-y_j| ∣xi​−xj​∣+∣yi​−yj​∣，其中，|a|表示取a的绝对值。

牛牛在m个小镇建立了传送门，也就是说，牛牛可以在任何时候任何瞬间不花费任何代价，直接到达这m个小镇的任何一个。

牛牛一开始在小镇1，牛牛想按1到n的顺序访问所有小镇按顺序做任务，问牛牛需要走过的最短距离是多少。

牛牛可以提前到达某个小镇，但是必须做完前一个小镇的任务，才能做下一个小镇的任务。做任务本身不会增加距离。

I n p u t Input Input

第一行输入两个整数n,m，表示地图上小镇的数目和牛牛建立了传送门的小镇数量。
随后n行，其中第i行输入两个整数 x i , y i x_i, y_i xi​,yi​ ，第i个小镇的坐标。
随后一行输入m个整数，表示建立了传送门的小镇编号。
对于20%的数据有m=0。
对于40%的数据有m=1。
对于60%的数据有n,m≤300。
对于100%的数据有 1 ≤ n ≤ 5000 , 0 ≤ m ≤ n , − 10000 ≤ x i , y i ≤ 10000 1≤n≤5000,0≤m≤n,−10000≤x_i, y_i ≤10000 1≤n≤5000,0≤m≤n,−10000≤xi​,yi​≤10000。
数据保证没有任意两个小镇在同一坐标下。

O u t p u t Output Output

一行一个整数表示答案。

S a m p l e Sample Sample I n p u t Input Input

6 2
-10 -10
10 10
0 0
1 -1
-1 1
2 1
3 6

S a m p l e Sample Sample O u t p u t Output Output

21

H i n t Hint Hint

牛牛一开始在小镇1，完成任务后，传送到小镇6。
步行至小镇2，累计17点距离，完成任务后，传送到小镇3。
在小镇3完成任务，累计17点距离。
步行到小镇4完成任务，累计19点距离， 传送到小镇3。
步行到小镇5完成任务，累计21点距离。
传送到小镇6并完成任务。
共计21点距离。

T r a i n Train Train o f of of T h o u g h t Thought Thought

因为不可能存在i点到i+1点需要两次传送或者需要传送到一个点走一个点再到i+1
所以直接从1for到n，判断是直接走，还是传送到某一个点再到i+1点

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int A[2][10250], B[10250];
int n, m, Ans;

int kd(int l, int r)
{return abs(A[0][l] - A[0][r]) + abs(A[1][l] - A[1][r]);}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%d%d", &A[0][i], &A[1][i]);
	for(int i = 1; i <= m; ++i)
		scanf("%d", &B[i]);
	for(int i = 1; i < n; ++i)
	{
		int k = kd(i, i + 1);
		for(int j = 1; j <= m; ++j)
			k = min(k, kd(B[j], i + 1));
		Ans += k;
	}
	printf("%d", Ans);
	return 0;
}