#P3363. [Usaco2004 Feb]Cow Marathon 奶牛马拉松

[Usaco2004 Feb]Cow Marathon 奶牛马拉松

题目描述

农夫约翰要给奶牛设计一条尽可能长的马拉松路线。地图有 NN 个农场、MM 条连接农场的双向道路,任意两个不同农场之间恰有一条不重复经过农场的路径。

两农场之间的距离为这条路径上各道路的长度之和。求任意两个农场之间的最大距离。

输入格式

第一行两个整数 N,MN,M,表示农场数和道路数。农场编号为 11 到 NN,2≤N≤400002\le N\le40000,道路构成一棵树,故 M=N−1M=N-1。

接下来 MM 行,每行给出三个整数 F1,F2,LF_1,F_2,L 和一个字符 DD。它们表示从 F1F_1 到 F2F_2 的道路长度为 LL(1≤L≤10001\le L\le1000),方向为 DD。DD 是 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
52

从农场 22 经过 4,1,6,34,1,6,3 到 55,总距离为 20+3+13+9+7=5220+3+13+9+7=52。

USACO 原题 · 原题引用的地图定义