#P3363. [Usaco2004 Feb]Cow Marathon 奶牛马拉松
[Usaco2004 Feb]Cow Marathon 奶牛马拉松
题目描述
农夫约翰要给奶牛设计一条尽可能长的马拉松路线。地图有 个农场、 条连接农场的双向道路,任意两个不同农场之间恰有一条不重复经过农场的路径。
两农场之间的距离为这条路径上各道路的长度之和。求任意两个农场之间的最大距离。
输入格式
第一行两个整数 ,表示农场数和道路数。农场编号为 到 ,,道路构成一棵树,故 。
接下来 行,每行给出三个整数 和一个字符 。它们表示从 到 的道路长度为 (),方向为 。 是 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
从农场 经过 到 ,总距离为 。