Description
给定一个 $n \times n\ (1 \leq n \leq 2 \times 10^4)$ 的网格图,走一条边用时 $2$,只能在特定的 $m\ (1 \leq m \leq 10^5)$ 个点转向,转向用时 $1$,求从 $(x_1,x_2)$ 到 $(y_1, y_2)$ 的最短用时。
Source
Solution
考虑 分层图最短路 。
对于样例:
Sample Input
1 | 6 9 |
Sample Output
1 | 27 |
题目所给的图:
我们按照输入的顺序给这些点标上号(包括起点和终点),共 $m + 2$ 个点。
设 $n = m + 2$,表示点的数量。起点为 $10$ 号节点,终点为 $11$ 号节点。
我们可以把图分成两层,其中第 $1$ 层为横向走,第 $2$ 层为纵向走。
先考虑横向走。将所有点以横坐标为第 $1$ 关键字,纵坐标为第 $2$ 关键字从小到大排序。排完序后,判断相邻两个点的横坐标是否相同,如果相同,则在它们两个点之间连一条边权为 两点纵坐标之差的两倍 的双向边。若可以连边 $u \leftrightarrow v$,则说明从点 $u$ 可以横向走到点 $v$,亦可以从点 $v$ 横向走到点 $u$ 。
图中可以连的边有:
$1 \leftrightarrow 2\\4 \leftrightarrow 11\\5 \leftrightarrow 6\\7 \leftrightarrow 8\\8 \leftrightarrow 9$
边权分别为 $8,4,8,4,2$ 。
纵向走同理。因为纵向走在第 $2$ 层,节点编号不能与第 $1$ 层相同,所以给第 $2$ 层编号全部 $+n$ 。然后将所有点以纵坐标为第 $1$ 关键字,横坐标为第 $2$ 关键字从小到大排序。比较相邻两点纵坐标,连边。若可以连边 $u \leftrightarrow v$,则说明从点 $u$ 可以纵向走到点 $v$,也可以从点 $v$ 纵向走到点 $u$ 。
图中可以连的边有:
$10+11 \leftrightarrow 1+11\\1+11 \leftrightarrow 7+11\\3+11 \leftrightarrow 5+11\\4+11 \leftrightarrow 9+11\\11+11 \leftrightarrow 6+11$
边权分别为 $2,8,4,4,2$ 。
接下来在两层 表示同个节点的点 之间连一条权值为 $1$ 的双向边,表示可以在该点改变方向,用时为 $1$ 。
注意起点和终点改变方向不需要 $1$ 的时间,所以在 起点 与 起点$ + n$ 之间,终点 与 终点$ + n$ 之间连一条边权为 $0$ 的双向边。
最后跑一遍起点到终点的最短路即是答案,时间复杂度为 $O(m\log m)$。
完整的图:
Code
1 |
|