Java问题描述：在听说美国肥胖流行之后，农夫约翰希望他的奶牛能够做更多的运动，因此他为了他的奶牛提交了马拉松申请，马拉松路线包括一系列农场对和它们之间的道路组成的路径。由于约翰希望奶牛尽可能的多运动，他想在地图上找到彼此距离最远的两个农场（距离是根据两个农场之间的道路的总长度来衡量的。）请帮助他确定这对最远的农场之间的距离。 输入格式：第一行是两个以空格符分隔的整数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

Java代码实现：

import java.io.*;
import java.util.Arrays;

public class Main {
    static int N = 10010, M = N * 2, idx = 1;
    static int[] h = new int[N], e = new int[M], w = new int[M], ne = new int[M];
    static int n, m, res = 0;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        Arrays.fill(h, -1);
        while (m-- > 0) {
            line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]), b = Integer.parseInt(line[1]), c = Integer.parseInt(line[2]);
            char d = line[3].charAt(0);
            int distance = getDistance(a, b, c, d);
            add(a, b, distance);
            add(b, a, distance);
        }

        spfa();

        for (int i = 1; i <= n; i++)
            res = Math.max(res, dist[i]);
        System.out.println(res);
    }

    private static void spfa() {
        Arrays.fill(dist, -0x3f3f3f);
        dist[1] = 0;

        for (int i = h[1]; i != -1; i = ne[i])
            dist[e[i]] = w[i];

        st[1] = true;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++)
                if (!st[j] && (t == -1 || dist[t] < dist[j]))
                    t = j;

            st[t] = true;

            for (int j = h[t]; j != -1; j = ne[j]) {
                int ver = e[j], distance = w[j];
                if (dist[ver] < dist[t] + distance) {
                    dist[ver] = dist[t] + distance;
                }
            }
        }
    }

    private static int getDistance(int a, int b, int c, char d) {
        if (d == 'N') return c;
        else if (d == 'S') return c;
        else if (d == 'W') return c;
        else return c;
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}