题目链接: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
样例解释
牛牛一开始在小镇 ,完成任务后,传送到小镇 。
步行至小镇 ,累计 点距离,完成任务后,传送到小镇 。
在小镇 完成任务,累计 点距离。
步行到小镇 完成任务,累计 点距离, 传送到小镇 。
步行到小镇 完成任务,累计 点距离。
传送到小镇 并完成任务。
共计 点距离。
思路
这道题是一道模拟。
因为我们要从 按顺序走每一个点,那我们从 走到 ,就有两种方法:
- 从 直接走到
- 先传送到一个传送门,然后再从传送门走到
那就每一次都这样算一遍距离,找到距离最小的。
时间复杂度是
比赛时
看到题目有点蒙,想了一会想到了可以 ,看了看范围就码了出来。
代码
#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; }