在听说美国肥胖流行之后，农夫约翰希望他的奶牛能够做更多的运动，因此他为了他的奶牛提交了马拉松申请，马拉松路线包括一系列农场对和它们之间的道路组成的路径。由于约翰希望奶牛尽可能的多运动，他想在地图上找到彼此距离最远的两个农场（距离是根据两个农场之间的道路的总长度来衡量的。）请帮助他确定这对最远的农场之间的距离。 输入格式：第一行是两个以空格符分隔的整数n和m；接下来的第二行到第m+1行，每行包含4个以空格分开的元素x，y，w和d来描述一条道路，其中x和y是一条长度为w的道路相连的两个农场的编号，d是字符N.E.S.或W，表示从x到y的道路的方向。 输出格式：给出最远的一对农场之间距离的整数。 输入样例： 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 提示:马拉松路线一定是简单路径，实际上是一颗带权无向树（作为带权无向图处理），样例中的图如下图所示：题目就是求两个顶点之间的最大长度。图中顶点编号是1-n。由图可知，样例中的最长马拉松路线是从2经过4 1 6 3到达5，长度就是20+3+13+9+7=52. 代码实现

以下是Python3代码实现：

from collections import deque

# 定义边的结构体
class Edge:
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

n, m = map(int, input().split())

# 初始化邻接表和入度数组
edges = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

# 读入边并建图
for i in range(m):
    x, y, w, d = input().split()
    x, y, w = int(x), int(y), int(w)
    # 将有向边转化为无向边
    if d == 'N':
        edges[x].append(Edge(y, w))
        edges[y].append(Edge(x, w))
    elif d == 'S':
        edges[x].append(Edge(y, w))
        edges[y].append(Edge(x, w))
    elif d == 'W':
        edges[x].append(Edge(y, w))
        edges[y].append(Edge(x, w))
    elif d == 'E':
        edges[x].append(Edge(y, w))
        edges[y].append(Edge(x, w))

# 拓扑排序
q = deque()
for i in range(1, n + 1):
    for e in edges[i]:
        indegree[e.to] += 1
for i in range(1, n + 1):
    if indegree[i] == 0:
        q.append(i)
dist = [-1] * (n + 1)
dist[q[0]] = 0
while q:
    u = q.popleft()
    for e in edges[u]:
        dist[e.to] = max(dist[e.to], dist[u] + e.weight)
        indegree[e.to] -= 1
        if indegree[e.to] == 0:
            q.append(e.to)

# 输出结果
print(max(dist))

时间复杂度为 O(n + m)，其中n为顶点数，m为边数。