用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.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 1010, M = 20010;
    static int n, m;
    static int idx;
    static int[] h = new int[N];
    static int[] e = new int[M], w = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();

        Arrays.fill(h, -1);

        while (m-- > 0) {
            int a = scan.nextInt(), b = scan.nextInt(), d = scan.nextInt(), c = 0;
            char ch = scan.next().charAt(0);
            if (ch == 'N') c = 1;
            else if (ch == 'E') c = 2;
            else if (ch == 'S') c = 3;
            else if (ch == 'W') c = 4;

            if (c == 1) add(a, b, d);
            else if (c == 2) add(a, b, -d);
            else if (c == 3) add(b, a, d);
            else if (c == 4) add(b, a, -d);
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            dijkstra(i);
            for (int j = 1; j <= n; j++) {
                res = Math.max(res, dist[j]);
            }
        }

        System.out.println(res);
    }

    private static void dijkstra(int start) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, false);

        dist[start] = 0;
        for (int i = 0; i < n; 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 k = e[j];
                if (dist[k] > dist[t] + w[j]) {
                    dist[k] = dist[t] + w[j];
                }
            }
        }
    }

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

时间复杂度：O(n(m + n log n))