#P1984. Navigation Nightmare
Navigation Nightmare
描述
农场主约翰的田园社区有N个农场,通常标号/标签为1..N。一系列M条不同长度的垂直和水平道路连接这些农场。这些农场的地图可能看起来像下面的插图,其中农场被标记为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,因为鲍勃想知道的是这两座农场之间的“曼哈顿距离”。
在二维平面上,两个点和之间的曼哈顿距离定义为(这相当于一辆出租车在完美网格状的城市街道上行驶,从点到点所需行驶的总距离)。
当鲍勃询问某一对农场之间的距离时,约翰可能还没有足够的信息来推断出它们之间的距离;在这种情况下,约翰会深表歉意,并回复“-1”。
输入
*第1行: 两个用空格分隔的整数: N 和 M。
*第2行至第M+1行: 每行包含四个用空格分隔的元素: F1、F2、L 和 D,用于描述一条道路。F1 和 F2 是这条道路连接的两个农场的编号。L 是这条道路的长度。D 是一个字符,表示道路从 F1 到 F2 的方向,可以是 'N'(北)、'E'(东)、'S'(南)或 'W'(西)。
*第M+2行: 一个单独的整数,代表农夫鲍勃提出的查询次数。
*第M+3行至第M+K+2行: 每行对应鲍勃提出的一个查询,包含三个用空格分隔的整数: F1、F2 和 I。 F1 和 F2 是查询中涉及的两个农场的编号。 I 是一个索引,表示鲍勃是在数据输入到哪一条道路(即第 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 二月赛