RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:280065

还原地图 - 题库 - RQNOJ
PID373 / 还原地图
题目描述

农夫John有n个农场,农场之间有m条路。所有的路都是水平或竖直的。例如一个有7个农场的地图,农场之间路中括号的数字代表了路的长度

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

      |                 |

      (3)                |

      |                (7)

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

      |                 |

      (2)                F5

      |

      F7

可以看到,一个农场最多能直接通向4个农场(南北西东)。每条路的两端都会有农场,没有路会相交。任何两个农场间只有一条通路(由数条路组成)。

不幸的是,John丢了农场的地图,于是他要用电脑上的备份文件还原这份地图。备份文件的数据是一条一条的,每一条还原一条路,表示如下:

F1 F2 L D

其中,F1,F2,L为整数,表示F1距离F2长为L。D为’E’,’W’,’S’,’N’中的一个,表示从F1到F2的方向。

在John还原地图的同时,他的邻居农夫Bob会不断的对John提问,格式如下:

F1 F2 I

表示Bob会在John还原第I条数据后询问F1与F2的曼哈顿距离(两点x坐标之差的绝对值加y坐标之差的绝对值)

如果这时John已经知道了F1,F2之间的曼哈顿距离,就会回答Bob;如果不是只能很抱歉。

你的程序将读入所有地图的备份数据以及Bob的询问,对于每个询问给出回答。如果还不知道两点间的曼哈顿距离则输出"-1"

输入格式

第一行:两个整数 N和M(2<=N<=40000,1<=M<40000)

第二行到第M+1行:每行包含F1 F2 L D,为地图的备份数据。 (1<=F1,F2<=N;1<=L<=1000)

第M+2行:一个整数K,表示Bob的询问的个数(1<=K<=10000)

第M+3到M+K+2行:每行包含F1 F2 I,为Bob的询问。

输出格式

共K行,对Bob的每个询问一次给出回答。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论