Problem:


サージェント・ライアン

 「ライアン軍曹を救え」という指令のもと、アイヅ軍の救出部隊はドイツリーの水上都市で敵軍と激しい戦闘を繰り広げていました。彼らは無事に軍曹と合流しましたが、敵の戦車が多く、救出ヘリを呼べずにいました。そこで、彼らは敵の戦車を混乱させるため、都市にある橋を全て爆破するという作戦を実行することにしました。

作戦はすぐに司令部に伝えられ、救出ヘリの準備が進められました。救出ヘリを飛ばすためには、いつ橋が全て爆破されるかを予測しなければなりません。軍のプログラマであるあなたの任務は、救出部隊が全ての橋の爆破に必要な時間を計算することです。

水上都市は N 個の島で構成されており、島と島との間には橋がかかっています。すべての島はツリー状に繋がっています(下図参照)     。ある島からある島への経路は、一通りだけ存在します。各橋を渡るには、橋ごとに決められた時間がかかり、どちらの方向にもその時間で橋を渡ることが可能です。

 救出部隊はボートなど水上を移動する手段を持っていないので島と島の間を移動するには橋を通る他ありません。救出部隊は、その時いる島に隣接している橋のうち、必要なものを一瞬で爆破することができます。救出部隊が全ての橋を爆破するのに必要な最小の時間はいくらでしょうか。ただし、島の中での移動時間は考えません。

 島の数、それぞれの橋情報を入力とし、橋を全て爆破するのに必要な最小の時間を出力するプログラムを作成してください。島はそれぞれ 1 から N の番号で表されます。橋は N-1 本あります。橋情報は、その橋が隣接している二つの島の番号(a, b)と、その橋を渡るのに必要な時間 t で構成されます。救出部隊は島番号 1 の島からスタートするものとします。

Input

複数のデータセットの並びが入力として与えられる。入力の終わりはゼロひとつの行で示される。各データセットは以下の形式で与えられる。

N
a1 b1 t1
a2 b2 t2
:
aN-1 bN-1 tN-1

入力はすべて整数で与えられる。1 行目に島の数 N (2 ≤ N ≤ 20) が与えられる。

続く N-1 行に i 番目の橋の情報が与えられる。 ai, bi, ti (1 ≤ ti ≤ 500) は、i 番目の橋を通って島 ai と島 bi の間を時間 ti で移動できることを表す。

データセットの数は 100 を超えない。

Output

データセットごとに、橋を全て爆破するのに必要な最小の時間を1行に出力する。

Sample Input

7
1 2 5
2 3 2
3 4 3
2 5 3
5 6 3
5 7 8
0

Output for the Sample Input

12



Sample input:
7
1 2 5
2 3 2
3 4 3
2 5 3
5 6 3
5 7 8
0


Sample output:
12

Submission status: Wrong Answer

Solution code:
N = int(input())
R = [[0 for i in range(N+1)] for i in range(N+1)]

def dfs_max(cur, pre):
    print(cur)
    _max = -R[cur][pre]
    for i in range(N+1):
        if R[cur][i] > 0 and i != pre:
            _max = max(_max, dfs_max(i, cur) + R[cur][i])

    print('max : %d' % _max)
    return _max

total = 0
for i in range(N-1):
    a, b, t = list(map(int, input().split()))
    R[a][b] = t
    R[b][a] = t
    total += (t * 2)

for i in range(2, N+1):
    spam = [x for x in R[i] if x > 0]
    if(len(spam) <= 1):
        total -= (spam[0] * 2)

print((total - dfs_max(1, 0)))

Submission status: Wrong Answer

Solution code:
N = int(input())
R = [[0 for i in range(N+1)] for i in range(N+1)]


def dfs_max(cur, pre):
    _max = -R[cur][pre]
    for i in range(N+1):
        if R[cur][i] > 0 and i != pre:
            _max = max(_max, dfs_max(i, cur) + R[cur][i])
#    print('max : %d' % _max)
    return _max

total = 0
for i in range(N-1):
    a, b, t = list(map(int, input().split()))
    R[a][b] = t
    R[b][a] = t
    total += (t * 2)

for i in range(2, N+1):
    spam = [x for x in R[i] if x > 0]
    if(len(spam) <= 1):
        total -= (spam[0] * 2)

print((total - dfs_max(1, 0)))

Submission status: Wrong Answer

Solution code:
while(1):
    N=int(raw_input())
    if N==0: break
    A=[[0 for i in range(N)] for j in range(N)]
    for i in range(N-1):
        a,b,t=map(int, raw_input().split())
        A[a-1][b-1]=t
        A[b-1][a-1]=t
        
    klist=[0]
    while len(klist)!=0:
        k=klist.pop(0)
        for i in range(N):
            if A[k][i]!=0:
                A[i][k]=0
                klist.append(i)
    for i in range(N):
        for j in range(N):
            if A[i][j]!=0 and sum(A[j])==0:
                A[i][j]=0
    
    def f(k):
        r=[]
        for i in range(N):
            if A[k][i]!=0:
                r.append( A[k][i] + f(i) )
        if len(r)!=0:
            return 2*sum(r)-max(r)
        else:
            return 0
    
    print f(0)

Submission status: Wrong Answer

Solution code:
while(1):
    N=int(raw_input())
    if N==0: break
    A=[[0 for i in range(N)] for j in range(N)]
    for i in range(N-1):
        a,b,t=map(int, raw_input().split())
        A[a-1][b-1]=t
        A[b-1][a-1]=t
        
    klist=[0]
    while len(klist)!=0:
        k=klist.pop(0)
        for i in range(N):
            if A[k][i]!=0:
                A[i][k]=0
                klist.append(i)
    for i in range(N):
        for j in range(N):
            if A[i][j]!=0 and sum(A[j])==0:
                A[i][j]=0
    
    def f(k):
        r=[]
        s=[0]
        for i in range(N):
            if A[k][i]!=0:
                ff=f(i)
                r.append( A[k][i] + ff[0])
                s +=  map(lambda x: x + A[k][i] , ff[1])
        if len(r)!=0:
            return sum(r),s
        else:
            return 0,s
    
    fans = f(0)
    print fans[0]*2 - max(fans[1])

Submission status: Wrong Answer

Solution code:
while(1):
    N=int(raw_input())
    if N==0: break
    A=[[0 for i in range(N)] for j in range(N)]
    for i in range(N-1):
        a,b,t=map(int, raw_input().split())
        A[a-1][b-1]=t
        A[b-1][a-1]=t
        
    klist=[0]
    while len(klist)!=0:
        k=klist.pop(0)
        for i in range(N):
            if A[k][i]!=0:
                A[i][k]=0
                klist.append(i)
    for i in range(N):
        for j in range(N):
            if A[i][j]!=0 and sum(A[j])==0:
                A[i][j]=0
    
    def f(k):
        s=[0]
        for i in range(N):
            if A[k][i]!=0:
                s +=  map(lambda x: x + A[k][i] , f(i))
        return s
    
    fans=f(0)
    print sum([sum(x) for x in A])*2 - max(fans)

Submission status: Wrong Answer

Solution code:
def distlists(A,s):
    ret=[0]
    for i in range(N+1):
        if A[s][i]!=0:
            a=A[s][i]
            B=A[:]
            B[s][i]=0
            B[i][s]=0
            ret+=[a+r for r in distlists(B,i)]
    return ret


while(1):
    N=int(raw_input())
    if N==0: break
    A=[[0 for i in range(N+1)] for j in range(N+1)]
    for i in range(N-1):
        [a,b,t]=map(int,raw_input().split())
        A[a][b]=t
        A[b][a]=t
    for i in range(2,N+1):
        if sum([b!=0 for b in A[i]])==1:
            for j in range(N+1):
                A[i][j]=0
                A[j][i]=0
    print sum(map(sum,A))-max(distlists(A,1))

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N == 0:break
    R = [[0 for i in range(N+1)] for i in range(N+1)]

    def dfs_max(cur, pre):
        _max = -R[cur][pre]
        for i in range(N+1):
            if R[cur][i] > 0 and i != pre:
                _max = max(_max, dfs_max(i, cur) + R[cur][i])
    #    print('max : %d' % _max)
        return _max

    total = 0
    for i in range(N-1):
        a, b, t = list(map(int, input().split()))
        R[a][b] = t
        R[b][a] = t
        total += (t * 2)

    for i in range(2, N+1):
        spam = [x for x in R[i] if x > 0]
        if(len(spam) <= 1):
            total -= (spam[0] * 2)

    print((total - dfs_max(1, 0)))

Submission status: Accepted

Solution code:
INF = 1<<30
while 1:
    n = input()
    if n == 0: break
    l = [[INF]*n for _ in range(n)]
    for i in range(n): l[i][i] = 0
    cnt = [0]*n
    ans = 0
    for _ in range(n-1):
        a, b, t = map(int, raw_input().split())
        a -= 1; b -= 1
        cnt[a] += 1; cnt[b] += 1
        l[a][b] = l[b][a] = t
        ans += 2*t
    for i in range(1,n):
        if cnt[i] == 1:
            for j in range(n):
                if l[i][j] != INF:
                    ans -= 2 * l[i][j]
                    l[i][j] = l[j][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                l[i][j] = min(l[i][j], l[i][k]+l[k][j])
    print ans - max(l[0])

Submission status: Accepted

Solution code:
from collections import deque
while 1:
    N = int(input())
    if N == 0:
        break

    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b, t = map(int, input().split())
        a -= 1; b -= 1
        G[a].append((b, t))
        G[b].append((a, t))
    D = [-1]*N; P = [0]*N
    que = deque([0])
    D[0] = 0
    while que:
        v = que.popleft()
        c = D[v]
        for w, d in G[v]:
            if D[w] != -1:
                continue
            D[w] = c + d
            P[w] = d
            que.append(w)
    ans = 0
    m = 0
    for i in range(N):
        if not i or len(G[i]) > 1:
            ans += P[i]*2
            m = max(m, D[i])
    ans -= m
    print(ans)

Submission status: Accepted

Solution code:
def dfs1(v, pv):
    for nv, _ in adj_list[v]:
        if nv==pv:
            continue
        
        is_leaf[v] = False
        dfs1(nv, v)
    
    return is_leaf
    
def dfs2(v, pv, d):
    dist[v] = d
    
    for nv, w in adj_list[v]:
        if nv==pv:
            continue
        
        dfs2(nv, v, d+w)
    
    return dist

while True:
    N = int(input())
    
    if N==0:
        break
    
    a, b, t = [], [], []
    adj_list = [[] for _ in range(N)]
    
    for _ in range(N-1):
        ai, bi, ti = map(int, input().split())
        a.append(ai-1)
        b.append(bi-1)
        t.append(ti)
        adj_list[ai-1].append((bi-1, ti))
        adj_list[bi-1].append((ai-1, ti))
        
    is_leaf = [True]*N
    dist = [-1]*N
    
    dfs1(0, -1)
    dfs2(0, -1, 0)
    
    tmp = 0
    
    for ai, bi, ti in zip(a, b, t):
        if (not is_leaf[ai]) and (not is_leaf[bi]):
            tmp += 2*ti
        
    ans = tmp
    
    for i in range(N):
        if not is_leaf[i]:
            ans = min(ans, tmp-dist[i])
    
    print(ans)

Submission status: Accepted

Solution code:
def tree_walk_1(start, parent=None):
    for i, t in adj[start]:
        if i != parent:
            P[i] = (start, t)
            C[start].append((i, t))
            tree_walk_1(i, start)

def tree_walk_2(start):
    global time
    notVisited[start] = False
    for c, t1 in C[start]:
        if notVisited[c]:
            time += 2 * t1
            tree_walk_2(c)
    p, t2 = P[start]
    if notVisited[p]:
        time += t2
        tree_walk_2(p)

from sys import stdin
f_i = stdin

while True:
    N = int(f_i.readline())
    if N == 0:
        break
    
    adj = [[] for i in range(N)]
    for i in range(N - 1):
        a, b, t = map(int, f_i.readline().split())
        a -= 1
        b -= 1
        adj[a].append((b, t))
        adj[b].append((a, t))
    
    # leaf cutting
    lf = []
    for i, a in enumerate(adj[1:], start=1):
        if len(a) == 1:
            lf.append(i)
    for l in lf:
        i, t = adj[l].pop()
        adj[i].remove((l, t))
    
    # root candidate
    rc = [i for i, a in enumerate(adj[1:], start=1) if len(a) == 1]
    if not rc:
        print(0)
        continue
    
    time_rec = []
    for r in rc:
        P = [None] * N
        P[r] = (r, 0)
        C = [[] for i in range(N)]
        tree_walk_1(r) #making a tree
        
        time = 0
        notVisited = [True] * N
        tree_walk_2(0)
        time_rec.append(time)
    
    print(min(time_rec))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:break
    edges = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, t = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append([b, t])
        edges[b].append([a, t])
    used = [False] * n
    is_leaf = [False] * n
    for i in range(1, n):
        if len(edges[i]) == 1:is_leaf[i] = True


    def check(x):
        used[x] = True
        times = [0]
        max_path = 0
        for to, t in edges[x]:
            if not used[to] and not is_leaf[to]:
                time, path = check(to)
                times.append(time + t * 2)
                max_path = max(max_path, path + t)
        return sum(times), max_path


    total_time, max_path = check(0)
    print(total_time - max_path)