{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eJohn是一个农场主,他有许多农场,每个农场里都会养一些牛,并且他的农场有一个特点,就是每两个农场之间,至多存在一条路线。他有时需要将某个农场的牛带到另一个农场去,但是,他的牛都懒散惯了,所以John想为他的牛找到一条最短的路线。先给出John的农场地图,请你为他计算某两个农场间的最短距离。\u003c/p\u003e\n"}},{"title":"输入格式","value":{"format":"HTML","content":"\u003cp\u003e第一行给出两个整数 $n,m(n,m\\le 40000)$,表示农场数和道路数。\u003c/p\u003e\n\u003cp\u003e接下来有 $m$ 行,每行给出三个整数 $a,b,c$ 和一个字符 $x$,表示农场 $a$ 到农场 $b$ 的有一条直接相连的长度为 $c$ 的道路,字符 $x$ 只会是$N,S,W,E$,表示north, south, west, east,指从农场a到农场b的道路的方向。注意:所有道路都是双向道路。\u003c/p\u003e\n\u003cp\u003e接下来一行给出一个整数 $k(1\\le k\\le10000)$,表示询问次数。\u003c/p\u003e\n\u003cp\u003e接下来有 $k$ 行,每行给出两个整数 $a,b$,表示询问农场 $a$ 到农场 $b$ 的最短距离。\u003c/p\u003e\n\u003cb\u003e本题为POJ的题目,请使用G++提交,并且头文件中不能包含unordered_map。\u003c/b\u003e"}},{"title":"输出格式","value":{"format":"HTML","content":"\u003cp\u003e对于每个询问,输出农场 $a$ 到农场 $b$ 的最短距离。\u003c/p\u003e\n\u003cb\u003e每行输出末尾不能有多余空格。\u003c/b\u003e"}},{"title":"输入样例","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e7 6\n1 6 13 E\n6 3 9 E\n3 5 7 S\n4 1 3 N\n2 4 20 W\n4 7 2 S\n3\n1 6\n1 4\n2 6\n\u003c/pre\u003e"}},{"title":"输出样例","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e13\n3\n36\n\u003c/pre\u003e"}}]}