Description

\\n【题意】20241008scy修改题意
\\r\\n一个二维平面，有 $N$ 个坐标都为整数的点，点编号为 $1$ 到 $N$。
\\r\\n两点的距离为曼哈顿距离。$(x1, y1)$ 和 $(x2, y2)$ 间的曼哈顿距离定义为 $|x1 − x2| + |y1 − y2|$。
\\r\\n现在想要知道只通过前$K$ 条的信息，判断两个点的两点的曼哈顿距离。
\\r\\n
\\r\\n\\r\\n【输入格式】
\\r\\n• 第一行：两个整数 $N$ 和 $Q$，$1 \\\\le N \\\\le 40000, 1 \\\\le Q \\\\le 50000$
\\r\\n• 下来 $Q$ 行。每行三个整数一个字母：$U$，$V$，$L$，$C$。字母$C$是 $E$、$S$、$W$ 和 $N$ 中的一个。表示点$U$ 在点$V$ 的东E、南S、西W、北N方向，且距离为$L$。$1 \\\\le U, V \\\\le N, 1 \\\\le L \\\\le 1000$
\\r\\n• 下来一个整数 $M$，表示询问的次数。
\\r\\n• 下来 $M$ 行。每行一个询问，三个整数 $U$ ， $V$，$K$ ，表示询问的是只通过前 $K$ 条信息，点 $U$ 和点$V$ 间的曼哈顿距离，$1 \\\\le U, V \\\\le N$
\\r\\n
\\r\\n【输出格式】
\\r\\n• 每个询问输出一行，输出两点间的曼哈顿距离，如果前K条信息还不足以得知答案，输出 −1。
\\r\\n
\\r\\n【样例输入】
\\r\\n7 6
\\r\\n1 6 13 E
\\r\\n6 3 9 E
\\r\\n3 5 7 S
\\r\\n4 1 3 N
\\r\\n2 4 20 W
\\r\\n4 7 2 S
\\r\\n3
\\r\\n1 6 1
\\r\\n1 4 3
\\r\\n2 6 6
\\r\\n
\\r\\n【样例输出】
\\r\\n13
\\r\\n-1
\\r\\n10
\\r\\n
\\r\\n【解释】
\\r\\n最后一个询问中，6 和 2 的南北距离为 3，东西距离为 7，故答案为 10
\\n

状态	递交者	时间	内存	语言	代码	递交时间
AC	huangjunhao	10ms	5.7 MiB	C++	1.4 KiB	2024-10-21 15:43:42
AC	Hansang1	11ms	5.2 MiB	C++	1.6 KiB	2024-10-16 19:12:48

统计

递交统计

USACO（48）并查集3：导航难题[Navigation Nightmare&#44; 2004 Feb]

信息

状态

开发

支持

关于

还没有账户？

登录

USACO（48）并查集3：导航难题[Navigation Nightmare, 2004 Feb]