#P3362. [Usaco2004 Feb]Navigation Nightmare 导航噩梦

    ID: 2551 传统题 1500ms 512MiB 尝试: 201 已通过: 92 难度: 5 上传者: 标签>难度分类普及+/提高-数据结构带权并查集离线与分治查询排序路径压缩按大小合并CF1700离线Green

[Usaco2004 Feb]Navigation Nightmare 导航噩梦

[USACO 2004 Feb] Navigation Nightmare 导航噩梦

题目描述

农夫约翰的村庄里有 NN 个农场。农场编号为 11 到 NN。MM 条道路都是水平或竖直的;道路之间不交叉,农场只位于道路端点,每个道路端点都有一个农场。每个农场在东、西、南、北四个方向上至多各有一条相连的道路。任意两个农场之间恰好有一条简单路径。 图中的农场用 F1 到 F7 表示,括号中为道路长度。示意图不按比例绘制。

F1 --- (13) ---- F6 --- (9) ----- F3
 |                                 |
(3)                                |
 |                                (7)
F4 --- (20) -------- F2            |
 |                                 |
(2)                               F5
 |
F7

约翰丢失了农场地图,只能逐条从计算机备份中恢复道路记录。例如,农场 2323 向北行进 1010 个单位可以到达农场 1717,农场 11 向东行进 77 个单位也可以到达农场 1717。

邻居鲍伯会在恢复地图的过程中询问两个农场的曼哈顿距离。点 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2) 的曼哈顿距离是 ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|;上例中农场 11 到 2323 的距离为 1717。若已恢复的道路信息不足以确定距离,约翰回答 −1-1。

输入格式

从标准输入读入。第一行是两个整数 N,MN,M,表示农场数和道路数。接下来 MM 行,每行给出三个整数和一个字符 F1,F2,L,DF_1,F_2,L,D,表示从农场 F1F_1 沿方向 DD 行进 LL 个单位到达农场 F2F_2。DD 为 N(北)、E(东)、S(南)或 W(西)。

随后一行是整数 KK,表示询问数。接下来 KK 行,每行三个整数 A,B,IA,B,I,询问只知道前 II 条道路记录时农场 AA 与 BB 的曼哈顿距离。

输出格式

向标准输出按询问的输入顺序输出 KK 行。每行输出相应的距离;若无法确定,输出 −1-1。

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
13
-1
10

样例解释

第一问只知道第一条道路,已能确定 11 与 66 相距 1313。第二问时仍无法推出 11 与 44 的距离。最后一问中,农场 66 在农场 22 以北 33、以西 77,故距离为 1010。

数据范围与约定

2≤N≤40 0002\le N\le 40\,000,1≤M<40 0001\le M<40\,000,1≤L≤1 0001\le L\le 1\,000。各农场编号在 11 到 NN 之间。另有 1≤K≤10 0001\le K\le 10\,000,1≤I≤M1\le I\le M。