主题

主题

 
   

3362: [Usaco2004 Feb]Navigation Nightmare 导航噩梦

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3362

Description

    农夫约翰有N(2≤N≤40000)个农场,标号1到N,M(2≤M≤40000)条的不同的垂直或水

平的道路连结着农场,道路的长度不超过1000.这些农场的分布就像下面的地图一样,

图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场.此外,农场只处在道路的两端.道路不会交叉且每对农场间有且仅有一条路径.邻居鲍伯要约翰来导航,但约翰丢了农场的地图,他只得从电脑的备份中修复了.每一条道路的信息如下:

从农场23往南经距离10到达农场17

从农场1往东经距离7到达农场17

    当约翰重新获得这些数据时,他有时被的鲍伯的问题打断:“农场1到农场23的曼哈顿距离是多少?”所谓在(XI,Yi)和(X2,y2)之间的“曼哈顿距离”,就是lxl - X21+lyl - y21.如果已经有足够的信息,约翰就会回答这样的问题(在上例中答案是17),否则他会诚恳地抱歉并回答-1.

Input

    第1行:两个分开的整数N和M.

    第2到M+1行:每行包括4个分开的内容,F1,F2,三,D分别描述两个农场的编号,道路的长度,F1到F2的方向N,E,S,w.

    第M+2行:一个整数,K(1≤K≤10000),表示问题个数.

    第M+3到M+K+2行:每行表示一个问题,由3部分组成:Fi,F2,,.其中Fi和F2表示两个被问及的农场.而/(1≤J≤M)表示问题提出的时刻.J为1时,表示得知信息1但未得知信息2时.

Output

    第1到K行:每行一个整数,回答问题.表示两个农场间的曼哈顿距离.不得而知则输出-1.

Sample Input

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

Sample Output

13

-1

10

HINT

   在时刻1,约翰知道1到6的距离为13;在时刻3,1到4的距离仍然不知道;在时刻6,位置6向北3个距离,向西7个距离于位置2,所以距离为10.


个人解法:

由于横向与纵向的路径互不干扰。带权并查集即可。

注意,比方说(u,v,d,E),意味着不仅给出了东(E)西(W)向距离为d,也给出了南(S)北(N)向距离为0。

可以定义东(E)与北(N)为正坐标。如果出现了西(W)与南(S),就把路径变为相反数,或者把读入的点对的顺序交换(我是采用后者)。


代码如下:

https://code.csdn.net/snippets/2190026


成功踏入BZOJ第一版。本来还想卡一卡常当第一的……后来想想就算了吧……

 
 
评论