#P1984. Navigation Nightmare

Navigation Nightmare

描述

农场主约翰的田园社区有N个农场2<=N<=40,000(2 <= N <= 40,000),通常标号/标签为1..N。一系列M条1<=M<40,000(1 <= M < 40,000)不同长度的垂直和水平道路连接这些农场1<=长度<=1000(1 <= 长度 <= 1000)。这些农场的地图可能看起来像下面的插图,其中农场被标记为F1..F7以便清晰,并且连接农场之间的长度显示为(n):

       F1 --- (13) ---- F6 --- (9) ----- F3

        |                                 |

       (3)                                |

        |                                (7)

       F4 --- (20) -------- F2            |

        |                                 |

       (2)                               F5

        | 

       F7 

由于这是一个ASCII格式的示意图,当然,它并不完全按比例绘制。

每个农场最多可以通过四条道路直接与其他四个农场相连,这些道路分别朝向正北、正南、正东和/或正西方向。此外,农场只位于道路的端点处,且每条道路的每个端点都有一个农场。没有两条道路会相互交叉,并且任意两个农场之间都恰好存在一条路径

(即一系列相连的道路)将它们连接起来。

农夫约翰弄丢了他那份纸质版的农场地图,现在他正试图从电脑中的备份信息里重新构建这份地图。备份数据中的每条信息都类似下面这样,对应着每一条道路:

“有一条长度为10的道路从23号农场向北延伸至17号农场。”

“有一条长度为7的道路从1号农场向东延伸至17号农场。”

... 在约翰检索这些数据的过程中,他偶尔会收到来自邻居——方向感极差的农夫鲍勃的询问,比如:

“1号农场和23号农场之间的曼哈顿距离是多少?”

每当鲍勃提出这样的问题时,约翰如果能回答就会告诉他(当然,有时他手头的数据还不够充分,无法得出答案)。在上面的例子中,答案应该是17,因为鲍勃想知道的是这两座农场之间的“曼哈顿距离”。

在二维平面上,两个点x1,y1(x1, y1)x2,y2(x2, y2)之间的曼哈顿距离定义为x1x2+y1y2|x1 - x2| + |y1 - y2|(这相当于一辆出租车在完美网格状的城市街道上行驶,从(x1,y1)(x1, y1)点到(x2,y2)(x2, y2)点所需行驶的总距离)。

当鲍勃询问某一对农场之间的距离时,约翰可能还没有足够的信息来推断出它们之间的距离;在这种情况下,约翰会深表歉意,并回复“-1”。

输入

*第1行: 两个用空格分隔的整数: N 和 M。

*第2行至第M+1行: 每行包含四个用空格分隔的元素: F1、F2、L 和 D,用于描述一条道路。F1 和 F2 是这条道路连接的两个农场的编号。L 是这条道路的长度。D 是一个字符,表示道路从 F1 到 F2 的方向,可以是 'N'(北)、'E'(东)、'S'(南)或 'W'(西)。

*第M+2行: 一个单独的整数K1K10,000 K(1 ≤ K ≤ 10,000),代表农夫鲍勃提出的查询次数。

*第M+3行至第M+K+2行: 每行对应鲍勃提出的一个查询,包含三个用空格分隔的整数: F1、F2 和 I。 F1 和 F2 是查询中涉及的两个农场的编号。 I 是一个索引1IM(1 ≤ I ≤ M),表示鲍勃是在数据输入到哪一条道路(即第 I 条道路)之后提出这个查询的。 数据索引 1 对应输入数据的第 2 行(即第一条道路的信息)。 数据索引 2 对应第 3 行,以此类推。

输出

第1行至第K行:每行输出一个整数,作为对鲍勃每个查询的回应。每行应包含一个距离测量值(即两个农场之间的曼哈顿距离),或者如果无法确定合适的距离(即数据不足,无法根据当前已输入的道路信息计算出两农场间的曼哈顿距离),则输出 -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

提示

在第1时刻,农夫约翰知道1到6的距离是13。在第3时刻,1到4的距离仍然未知。最后,位置6位于2的西面3个单位和北面7个单位,因此距离是10。

来源

USACO 2004 二月赛