回家 (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

樣例輸入

樣例輸出

樣例解釋

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

樣例輸入

樣例輸出

提示

資料范圍

對于 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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198800.html

標籤：其他

上一篇：unity第三人稱視角下的攝像機控制及防穿墻

下一篇：2020年第11屆藍橋杯 Java B組省賽真題詳解及小結【第2場省賽 2020.10.17】

兔兔 的 題解 —— 2020 CSP-J 多校賽 T4

回家 (home)

題目限制

題目知識點

題目來源

題目

題目背景

題目描述

格式

輸入格式 (home.in)

輸出格式 (home.out)

樣例

樣例1

樣例輸入

樣例輸出

樣例解釋

樣例2

樣例輸入

樣例輸出

提示

資料范圍

思路

分析

代碼

兔兔的題解 —— 2020 CSP-J 多校賽 T4