---

B. 2D Traveling

原创 于 2023-09-12 13:36:00 发布 · 粉丝可见 · 205 阅读 · 0 · 1 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132829635

题目：

样例：

cobol<br/>5<br/>6 2 3 5<br/>0 0<br/>1 -2<br/>-2 1<br/>-1 3<br/>2 -2<br/>-3 -3<br/>2 0 1 2<br/>-1000000000 -1000000000<br/>1000000000 1000000000<br/>7 5 4 2<br/>154 147<br/>-154 -147<br/>123 456<br/>20 23<br/>43 20<br/>998 244<br/>353 100<br/>3 1 3 1<br/>0 10<br/>1 20<br/>2 30<br/>4 3 2 4<br/>0 0<br/>-100 100<br/>-1 -1<br/>-1 0<br/>

4 4000000000 0 22 1

思路：

根据题目意思，有三种情况，

第一种 起点以及终点都在 大城市 k 内，那么它们之间的票价就是  0

第二种 起点和终点都不在大城市内，那么我们先计算起点到终点之间的票价，再分别从大城市范围的诚实点中找到票价最低点，然后比较我们中间路径最短点的票价与我们直接起点到终点之间的票价，就是我们最低票价

第三种 起点与终点，任意一个是在大城市内，在这里，我们找到不在大城市内的往大城市范围的城市点中找到最短票价，与我们直接起点到终点之间的票价，就是我们最低票价。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define INF 0x3f3f3f3f3f3f3f3f3f
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
using PII = pair<int,int>;
 
PII v[N];	// 存储城市坐标点
int n,k,s,e;	// 分别是 城市数量，大城市范围，起点城市，重点城市
 
inline int Dis(int a,int b)
{
	return (abs(v[a].x - v[b].x) + abs(v[a].y - v[b].y));
}
 
inline void solve()
{
	cin >> n >> k >> s >> e;
	for(int i = 1;i <= n;++i)
	{
		int x,y;
		cin >> x >> y;
		v[i] = {x,y};
	}
	
	// 第一种情况 如果起点与终点都在大城市范围内
	// 最低票价直接是 0
	if(s <= k && e <= k)
	{
		puts("0");
		return ;
	}
	
	// 第二种情况 如果起点与终点都不在大城市范围内
	if(s > k && e > k)
	{
		// 先计算起点直接到终点的票价
		int now = Dis(s,e);
		
		// 定义中间票价为正无穷
		int dis_s = INF;
		int dis_e = INF;
		
		// 遍历大城市寻找中间城市点中的最低票价
		for(int i = 1;i <= k;++i)
		{
			dis_s = min(dis_s,Dis(s,i));
			dis_e = min(dis_e,Dis(e,i));
		}
		
		// 比较我们中间路径最短点的票价与我们直接起点到终点之间的票价
		// 输出最低票价
		cout << min(now,(dis_s + dis_e)) << endl;
		return ;
	}
	
	// 第三种情况 起点与终点任意一点在大城市范围内
	
	// 还是一样，先计算起点直接到终点的票价
	int now = Dis(s,e);
	
	// 找到在大城市外的城市点
	if(s < e) swap(s,e);
	
	// 定义大城市外的城市点票价为正无穷
	int dist = INF;
	
	// 遍历大城市寻找大城市外的城市点最低票价
	for(int i = 1;i <= k;++i)
	{
		dist = min(dist,Dis(s,i));
	}
	
	// 输出哪个是最低票价
	cout << min(now,dist) << endl;
	return ;
}
 
 
signed main()
{
//	freopen("a.txt", "r", stdin);
//	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：