#1019. [USACO 2004 Feb] Cow Marathon
[USACO 2004 Feb] Cow Marathon
Description
农夫约翰有 N 个农场,标号为 1 到 N。有 M 条不同的垂直或水平的道路连接着农场,道路的长度均不超过 1000。每个农场最多能在东西南北四个方向连接 4 个不同的农场。所有的道路都是双向的,任意两条道路都不会交叉,且任意两个农场间有且仅有一条路径。
最近美国过度肥胖非常普遍,农夫约翰为了让他的奶牛多做运动,举办了奶牛马拉松.马拉松路线要尽量长,所以,告诉你农场的地图,请帮助约翰寻找两个最远农场间的距离.
Input
第 1 行:两个分开的整数 N 和 M.
第 2 到 M+1 行:每行包括 4 个分开的内容,F1,F2,L,D 分别描述两个农场的编号,道路的长度,F1 到 F2 的方向 N,E,S,W.
Output
一个整数,表示最远两个衣场间的距离.
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
Sample Output
52
Hint
N, M ⩽ 4×10^4