3624: 平面旅行(第六轮02)
题目描述
牛牛最近在玩某款游戏，其地图可以看成一个平面直角坐标系。
地图上存在 n 个小镇，小镇从 1 到 n 编号。第 i 个小镇的坐标为(xi, yi )
。定义两个小镇的距离为曼哈顿距离，比如小镇 i 到小镇 j 的距离为|xi − xj | + |yi − yj |，其中， |a|表示取 a 的绝对值。
牛牛在 m 个小镇建立了传送门，也就是说，牛牛可以在任何时候任何瞬间不花 费任何代价，直接到达这 m 个小镇的任何一个。
牛牛一开始在小镇 1，牛牛想按 1 到 n 的顺序访问所有小镇按顺序做任务， 问牛 牛需要走过的最短距离是多少。
牛牛可以提前到达某个小镇，但是必须做完前一个小镇的任务，才能做下一个小 镇的任务。做任务本身不会增加距离。
输入
第一行输入两个整数 n,m，表示地图上小镇的数目和牛牛建立了传送门的小镇数 量。
随后 n 行，其中第 i 行输入两个整数xi, yi，第 i 个小镇的坐标。 随后一行输入 m 个整数，表示建立了传送门的小镇编号。
对于20%的数据有 m=0。 对于40%的数据有 m=1。
对于60%的数据有n, m ≤ 300。
对于100%的数据有1 ≤ n ≤ 5000, 0 ≤ m ≤ n, −10000 ≤ xi, yi ≤ 10000 数据保证没有任意两个小镇在同一坐标下。
输出
一行一个整数表示答案。
样例输入 复制
6 2
-10 -10
10 10
0 0
1 -1
-1 1
2 1
3 6样例输出 复制
21提示
【样例 1 输入】
6 2
-10 -10
10 10
0 0
1 -1
-1 1
2 1
3 6
【样例 1 输出】
21
【样例 1 说明】
牛牛一开始在小镇 1，完成任务后，传送到小镇 6。
步行至小镇 2，累计 17 点距离，完成任务后，传送到小镇 3。 在小镇 3 完成任务，累计 17 点距离。
步行到小镇 4 完成任务，累计 19 点距离， 传送到小镇 3。
步行到小镇 5 完成任务，累计 21 点距离。 传送到小镇 6 并完成任务。
共计 21 点距离。
对于20%的数据有 m=0。 对于40%的数据有 m=1。
对于60%的数据有n, m ≤ 300。
对于100%的数据有1 ≤ n ≤ 5000, 0 ≤ m ≤ n, −10000 ≤ xi, yi ≤ 10000 数据保证没有任意两个小镇在同一坐标下。