#P3364. [Usaco2004 Feb]Distance Queries 距离咨询
[Usaco2004 Feb]Distance Queries 距离咨询
题目描述
有 个农场,编号为 到 。它们由 条双向道路连接,任意两个农场之间恰有一条简单路径。两农场的距离是这条路径上各条道路长度之和。
,。每条道路的长度是 到 的整数。
给定 次询问,每次求两座农场之间的距离。
输入格式
第一行两个整数 。
接下来 行,每行两个农场编号 、一个道路长度 和一个字符 。字符 N、E、S、W 表示从 到 的方位。每条道路均可双向通行。
接下来一行给出询问数 ,满足 。随后 行,每行两个农场编号。
输出格式
对每次询问输出一行一个整数,表示两座农场之间的距离。
样例
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 4
2 6
13
3
36