回家 (home)

題目限制

• 記憶體限制：512 MiB
• 時間限制：2000 ms
• 檔案輸入輸出
  • 輸入檔案：home.in
  • 輸出檔案：home.out

題目知識點

• 最短路
• 貪心

題目來源

2020 CSP-J 多校賽 T4

題目

題目背景

W Y WY WY 巨佬是個路癡，有一天他迷路了

題目描述

W Y WY WY 生活在一個 n × n n \times n n×n 的網格圖中，他在 ( s x , s y ) (s_x, s_y) (sx?,sy?) 這個地方迷路了，他的家在 ( f x , f y ) (f_x, f_y) (fx?,fy?) 這個地方
W Y WY WY 可以用一分鐘向上下左右任意一個方向移動一格
由于 W Y WY WY 是個路癡，所以他想要一些幫助
作為 W Y WY WY 的好友 14 14 14， 14 14 14 在網格圖中為 W Y WY WY 設定了一些傳送門，其中第 i i i 個傳送門的位置在 ( x i , y i ) (x_i, y_i) (xi?,yi?)
當 W Y WY WY 所在的位置與一個傳送點 橫坐標相同 或 縱坐標相同 時，那么 W Y WY WY 就可以 瞬間傳送到這個傳送門所在的位置，且 不花費任何時間
W Y WY WY 想知道他回家的 最短用時 是多少

格式

輸入格式 (home.in)

輸入第一行，包含兩個整數 n , m n, m n,m，表示 網格圖的大小 和 傳送門的個數
輸入第二行，包含四個整數 s x , s y , t x , t y s_x, s_y, t_x, t_y sx?,sy?,tx?,ty?，表示 W Y WY WY 迷路的位置 和 W Y WY WY 家的位置
接下來 m m m 行，每行包含兩個整數 x i , y i x_i, y_i xi?,yi?，表示 第 i i i 個傳送門的位置

輸出格式 (home.out)

輸出只有一行，表示最短用時

樣例

樣例1

樣例輸入

5 3
1 1 5 5
1 2
4 1
3 3

樣例輸出

5

樣例解釋

W Y WY WY 的家在 ( 5 , 5 ) (5, 5) (5,5)，他在 ( 1 , 1 ) (1, 1) (1,1) 這個地方迷路了
W Y WY WY 可以通過在 ( 4 , 1 ) (4, 1) (4,1) 的傳送門直接傳送到 ( 4 , 1 ) (4, 1) (4,1)
然后從 ( 4 , 1 ) → ( 4 , 2 ) → ( 4 , 3 ) → ( 5 , 3 ) → ( 5 , 4 ) → ( 5 , 5 ) (4, 1) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (5,3) \rightarrow (5, 4) \rightarrow (5, 5) (4,1)→(4,2)→(4,3)→(5,3)→(5,4)→(5,5)，用時為 5 5 5，可以證明這是最短用時

樣例2

樣例輸入

84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7

樣例輸出

42

提示

資料范圍

對于 100 % 100\% 100% 的資料， 1 ≤ n ≤ 1 0 9 1 \leq n \leq 10^9 1≤n≤109， 0 ≤ m ≤ m i n ( 3 × 1 0 5 , n 2 ) 0 \leq m \leq min(3 \times 10^5, n^2) 0≤m≤min(3×105,n2)， 1 ≤ s x , s y , t x , t y , x i , y i ≤ 1 0 9 1 \leq s_x, s_y, t_x, t_y, x_i, y_i \leq 10^9 1≤sx?,sy?,tx?,ty?,xi?,yi?≤109

思路

• 注意：以下說的 點，指 題目給出的起點，終點，和傳送門

假設中途不經過傳送門，則 s s s 與 t t t 的距離就是 ∣ s x ? t x ∣ + ∣ s y ? t y ∣ \mid s_x - t_x \mid + \mid s_y - t_y \mid ∣sx??tx?∣+∣sy??ty?∣，即兩點的曼哈頓距離，而且不受中途經過的點影響
對于第 i i i 個傳送門，從任意一個點 ( a , b ) (a, b) (a,b) 到它的距離就是 m i n ( ∣ a ? x i ∣ , ∣ b ? y i ∣ ) min(\mid a - x_i \mid, \mid b - y_i \mid) min(∣a?xi?∣,∣b?yi?∣)，只需要到達傳送門的 橫坐標 或者 縱坐標 即可
我們可以把 每個點 與 每個點 之間連接一條邊，跑一個 d i j k s t r a dijkstra dijkstra

分析

• 注意：以下說的 點，指 題目給出的起點，終點，和傳送門

由于 每個點 與 每個點 之間建一條邊，會花費很多的空間和時間
可以把 每個傳送門 進行按照 x x x 坐標 和 y y y 坐標 排序
分別把 第 i i i 個傳送門 和 第 i + 1 i + 1 i+1 傳送門連一條邊，每個傳送門與 起點和終點 連一條邊
那么為什么可以這樣做呢？以 x x x 坐標排序 ( y y y 坐標排序 同理) 為例：
假設 W Y WY WY 要從 A A A 傳送門 到 B B B 傳送門，必定要經過 A x A_x Ax? 到 B x B_x Bx? 之間的橫坐標
若中途有另外的傳送門 C C C，就可以從 A A A 到 C C C，再從 C C C 到 B B B，這樣 A A A 到 B B B 的距離也不會改變
（只需要在橫坐標相同的點中考慮一個點，因為這些點是可以隨意到達的；再把選中的這個點與其他的點連接即可，只是可以不需要把每個點都相連，只把橫坐標相鄰的點連邊即可，因為每個點可以通過相鄰的點到達其它點）
于是連接排序過后相鄰的點，便可以從每個點到每個點了，而不需要建很多的邊

代碼

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = 2e9;
const int MAXM = 3e5;
int N, M;
struct node // 存點 
{
	int X, Y;
	int Pos;
	node () { X = Y = 0; }
}S, T, P[MAXM + 5];
struct edge // 存圖 鏈式前向星 
{
	int to, dis, next;
	edge () { to = dis = next = 0; }
	edge (int tt, int dd, int nn) { to = tt, dis = dd, next = nn; }
	friend bool operator < (edge a, edge b) { return a.dis > b.dis; }
}G[MAXM * 6 + 5];
int head[MAXM + 5], cnt;
int Dis[MAXM + 5];
bool vis[MAXM + 5];

int Fabs(int x) { return x > 0 ? x : -x; } // 絕對值 
int Min(int a, int b) { return a < b ? a : b; } // 最小值 

void Read(int &n) // 讀入優化 
{
	n = 0;
	bool f = 1;
	char C = getchar();
	while (C < '0' || C > '9')
	{
		if (C == '-') f ^= 1;
		C = getchar();
	}
	while ('0' <= C && C <= '9')
	{
		n = (n << 3) + (n << 1) + (C ^ 48);
		C = getchar();
	}
	if (!f) n = -n;
}

bool cmpx(node a, node b) { return a.X < b.X; } // 按照橫坐標排序 
bool cmpy(node a, node b) { return a.Y < b.Y; } // 按照縱坐標排序 

void addEdge(int u, int v, int w) // 建邊
{
	G[++cnt] = edge(v, w, head[u]);
	head[u] = cnt;
}

int Dijkstra(int s, int t) // Dijkstra 最短路演算法 
{
	for (int i = 0; i <= M + 1; i++)
		Dis[i] = INF, vis[i] = 0;
	Dis[s] = 0;
	priority_queue<edge> q;
	q.push(edge(s, 0, 0));
	while (!q.empty())
	{
		int u = q.top().to; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i > 0; i = G[i].next)
		{
			int v = G[i].to, w = G[i].dis;
			if (Dis[u] + w < Dis[v]) {
				Dis[v] = Dis[u] + w;
				q.push(edge(v, Dis[v], 0));
			}
		}
	}
	return Dis[t];
}

int main()
{
	freopen("home.in", "r", stdin);
	freopen("home.out", "w", stdout);
	Read(N), Read(M);
	Read(S.X), Read(S.Y), Read(T.X), Read(T.Y);
	P[0] = S, P[M + 1] = T;
	addEdge(0, M + 1, Fabs(S.X - T.X) + Fabs(S.Y - T.Y));
	for (int i = 1; i <= M; i++)
	{
		Read(P[i].X), Read(P[i].Y);
		P[i].Pos = i;
		addEdge(0, i, Min(Fabs(P[0].X - P[i].X), Fabs(P[0].Y - P[i].Y)));
		addEdge(i, 0, Fabs(P[i].X - P[0].X) + Fabs(P[i].Y - P[0].Y));
		addEdge(i, M + 1, Fabs(P[i].X - P[M + 1].X) + Fabs(P[i].Y - P[M + 1].Y));
		addEdge(M + 1, i, Min(Fabs(P[M + 1].X - P[i].X), Fabs(P[M + 1].Y - P[i].Y)));
	}
	sort(P + 1, P + M + 1, cmpx);
	for (int i = 1; i < M; i++)
	{
		addEdge(P[i].Pos, P[i + 1].Pos, Fabs(P[i].X - P[i + 1].X));
		addEdge(P[i + 1].Pos, P[i].Pos, Fabs(P[i + 1].X - P[i].X));
	}
	sort(P + 1, P + M + 1, cmpy);
	for (int i = 1; i < M; i++)
	{
		addEdge(P[i].Pos, P[i + 1].Pos, Fabs(P[i].Y - P[i + 1].Y));
		addEdge(P[i + 1].Pos, P[i].Pos, Fabs(P[i + 1].Y - P[i].Y));
	}
	printf("%d\n", Dijkstra(0, M + 1));
	return 0;
}