题目链接:https://ac.nowcoder.com/acm/problem/213412

到主站看:https://blog.csdn.net/weixin_43346722/article/details/109521769

题目

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

地图上存在 个小镇,小镇从 编号。第 个小镇的坐标为 。定义两个小镇的距离为曼哈顿距离,比如小镇i到小镇j的距离为 ,其中, 表示取 的绝对值。

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

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

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

输入

第一行输入两个整数 ,表示地图上小镇的数目和牛牛建立了传送门的小镇数量。

随后 行,其中第 行输入两个整数 ,第 个小镇的坐标。

随后一行输入 个整数,表示建立了传送门的小镇编号。

对于 的数据有

对于 的数据有

对于 的数据有

对于 的数据有

数据保证没有任意两个小镇在同一坐标下。

输出

一行一个整数表示答案。

样例输入

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

样例输出

21

样例解释

牛牛一开始在小镇 ,完成任务后,传送到小镇
步行至小镇 ,累计 点距离,完成任务后,传送到小镇
在小镇 完成任务,累计 点距离。
步行到小镇 完成任务,累计 点距离, 传送到小镇
步行到小镇 完成任务,累计 点距离。
传送到小镇 并完成任务。
共计 点距离。

思路

这道题是一道模拟。

因为我们要从 按顺序走每一个点,那我们从 走到 ,就有两种方法:

  1. 直接走到
  2. 先传送到一个传送门,然后再从传送门走到

那就每一次都这样算一遍距离,找到距离最小的。

时间复杂度是

比赛时

看到题目有点蒙,想了一会想到了可以 ,看了看范围就码了出来。

图片说明

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m, x[5001], y[5001], z, fly[5001], ans, dis;
bool canfly[5001];

int getdis(int X, int Y) {
    return abs(x[X] - x[Y]) + abs(y[X] - y[Y]);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]);

    for (int i = 1; i <= m; i++) {
        scanf("%d", &z);
        canfly[z] = 1;
        fly[i] = z;
    }

    for (int i = 2; i <= n; i++) {
        if (canfly[i]) continue;

        dis = getdis(i - 1, i);//直接走
        for (int j = 1; j <= m; j++)//枚举每一个传送门到的点
            dis = min(dis, getdis(fly[j], i));//从传送门走

        ans += dis;
    }

    printf("%d", ans);

    return 0;
}