Sergeant Rian(AOJ No.0235)

1〜N+1の島にN個の橋がかけられてツリー構造になっている。
Nと各橋の接続関係と各橋をわたるのに必要な時間t1, t2, ..., tNが与えられる。
自分がいる島に隣接した橋を爆破することができる（爆破にかかる所要時間は０）。
島１からスタートして、全ての橋を爆破するのにかかる最小時間を求める。
制約
1 < N < 21
0 < t < 501

アルゴリズム

深さ優先で探索していき、リーフの親の島に達したら、そこからリーフへの橋を爆破し、その親へ移動するということを繰り返していく。
ただし、ルートからの距離が一番長くなるリーフの親の島への訪問は最後にし、その島へ行く場合には通った橋を爆破しながら進む。
こうすると一番長い経路を往復せずにすむので最短になる。

橋の長さ(移動に掛かる所要時間)の合計を求めておき、DFSして、リーフからその親への橋の移動時間を減算する。SUM (リーフが無い場合の経路長)
また、DFSしながら、ルートからリーフの親までの所要時間の最大値も計算しておく。MAX
戻る分の所要時間があるので、SUMを２倍する。ルートからの距離が一番長くなるリーフの親の島へ訪問した後戻る必要は無いのでその分を引けばいい。従って、2×SUM-MAXが答えとなる。

コード

import java.util.*;
public class aoj0235 {
	static final Scanner stdin = new Scanner(System.in);
	static int sum, maxLength;
	static ArrayList<Edge>[] adjList;
	static boolean[] used;
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		while (true) {
			int N = stdin.nextInt();
			if (N == 0) break;
			adjList = new ArrayList[N];
			used = new boolean[N];
			sum = 0;
			for (int i = 0; i < N; ++i) adjList[i] = new ArrayList<Edge>();
			while (--N > 0) {
				int a = stdin.nextInt()-1, b = stdin.nextInt()-1, t = stdin.nextInt();
				adjList[a].add(new Edge(a, b, t));
				adjList[b].add(new Edge(b, a, t));
				sum += t;
			}
			maxLength = 0;
			used[0] = true;
			rec(0, 0, 0);
			System.out.println(sum * 2 - maxLength);
		}
	}
	static void rec(int cur, int length, int preDist) {
		boolean isLeaf = true;
		for (Edge e: adjList[cur]) {
			if (!used[e.d]) {
				isLeaf = false;
				used[e.d] = true;
				rec(e.d, length+e.w, e.w);
				used[e.d] = false;
			}
		}
		if (isLeaf) {
			int l = length - preDist;
			sum -= preDist;
			maxLength = Math.max(maxLength, length - preDist);
		}
	}
	public static class Edge {
		int s, d, w;
		Edge(int s, int d, int w) { this.s = s; this.d = d; this.w = w; }
	}
}