poj1985java

根据提供的引用[1]，这是一道求解最远距离的问题，可以使用图论中的最短路算法来解决。而引用则提供了一种解决树上最远距离的方法，可以通过找到树的直径来解决。下面是一种Java实现的树的直径算法：

import java.util.*;

public class Main {
    static int N = 100010, idx;
    static int h[] = new int[N], e[] = new int[N << 1], ne[] = new int[N << 1], w[] = new int[N << 1];
    static int dist[] = new int[N];
    static boolean st[] = new boolean[N];
    static int n, res;

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            int a = scan.nextInt(), b = scan.nextInt(), c = scan.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1);
        Arrays.fill(st, false);
        dfs(idx);
        System.out.println(res);
    }

    static void dfs(int u) {
        st[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                dfs(j);
                if (dist[u] + w[i] > res) {
                    res = dist[u] + w[i];
                    idx = j;
                }
                dist[u] = Math.max(dist[u], dist[j] + w[i]);
            }
        }
    }

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