Problem:


Problem H : Dungeon (II)

あなたはとあるゲームの開発に携わっている。
そのゲームはランダムに生成されたダンジョンをプレイヤーが探索するというものである。
ゲームの仕様として、プレイヤーに予めダンジョンの危険度を提示し、生成されたダンジョンを探索するのか、それとも新しくダンジョンを生成しなおすかを、選択できるようにしたい。

このゲームで生成されるダンジョンにはn 個の部屋が存在しており、0から n-1 までの番号が割り振られている。
部屋と部屋は通路で結ばれている。部屋と部屋を結ぶ通路は、合計で n-1 本存在している。
通路はどちらの方向へも進むことができる。
また、部屋と部屋の間には距離が設定されている。
生成されたダンジョンではいくつかの通路を経由して、ある部屋から他のすべての部屋へ行くことが可能である。
そして、プレイヤーがゲームを行う際に、２つの異なる部屋がスタート地点とゴール地点として選ばれる。

あなたはダンジョンの評価を行うために、危険度の評価方法を決めることにした。
まず、ある部屋から別の部屋までに移動する際の危険度を、部屋間を最短で移動するために使う通路の中で、最もコスト高い通路の値とする。
そして、ダンジョンの危険度を、i < j となる部屋のペアの間を移動する際の危険度の総和とすることにした。

ランダムに生成されたダンジョンのが入力として与えられる。
まず、i < j となるすべての部屋のペアについて、移動する際の危険度を計算して欲しい。
そして、その総和を問題の答えとして出力せよ。

Input

入力は以下のフォーマットで与えられる。

n
a1 b1 c1 
.
.
.
an-1 bn-1 cn-1 

ai bi ci は 部屋 ai と bi　を結ぶ通路の距離がciであることを表す。

入力は以下の制約を満たす

2 ≤ n ≤ 200,000 

0 ≤ ai,bi < n

0 ≤ ci ≤ 100,000

Output

答えの値を1行に出力せよ

Sample Input 1

4
0 1 3
1 2 5
1 3 2

Sample Output 1

23

Sample Input 2

6
0 2 5
2 1 1
2 3 10
3 5 4
3 4 2

Sample Output 2

111



Sample input:
4
0 1 3
1 2 5
1 3 2


Sample output:
23

Submission status: Wrong Answer

Solution code:
#-*- coding:utf-8 -*-

#通路の構造体
class passage:
    
    def __init__(self,start,end,w):
        self.start = start
        self.end = end
        self.w = w

#ダンジョンの危険度を求める
n = int(raw_input())

#各通路の危険度を取得
passages = []
starts = [] #スタートになりうる数
for i in range(n-1):
    line = map(int, raw_input().split())
    passages.append(passage(line[0],line[1],line[2]))
    starts.append(line[1])

#危険度の総和を算出して出力
cost = 0
for p in passages:
    cost += p.w
    
print cost

Submission status: Wrong Answer

Solution code:
#-*- coding:utf-8 -*-

#ダンジョンの危険度を求める
n = int(raw_input())

#各通路の危険度を取得
passages = {} #経路

for i in range(n-1):
    line = map(int, raw_input().split())
    
    #入力された経路を追加
    if (line[0],line[1]) not in passages or passages[(line[0],line[1])] < line[2]:
        passages[(line[0],line[1])] = line[2]
    
    for k in passages.keys():
        if k[1] == line[0]:
            passages[(k[0],line[1])] = passages[k] + line[2]

print sum([passages[k] for k in passages])