TopCoder SRM 144 Div2 Level 3 [PowerOutage] の日本語解説
解法に感動した･･･
問題 : http://topcoder.bgcoder.com/print.php?id=284
重要なところ
The graph represented by the set of edges (fromJunction[i],toJunction[i]) will never contain a loop, and all junctions can be reached from junction 0.
まず、"all junctions can be reached from junction 0"が重要。
全ての道は0から始まり、続いている。
更に"will never contain a loop"が重要、道にループは無い。
発想
ということは、『行き止まりまで行ったら戻ってくる必要がある』。
更に、『最後に行く道は折り返す必要がないということ』。
ということは、『一番奥深い（コストの掛かる）道を最後に行けばいい』。
ということは、『一番奥深いとこ以外は、折り返して戻ってくる必要がある』。
結論
ということは、
『全ての道のコストを２倍したものから、
一番奥深い道のコストを引けばいい』
誰が思いつくんだよこんなの･･･
ちなみに
こんなサイトあったけど･･･
SRM 144 Div2.1100 PowerOutage
http://tomiflu.hatenablog.com/entry/20120503/13360556424行で解けた。わーい。
うわぁ、4行すげえ！
なーんて思っちゃうけど、問題によっては間違うので注意。
例えば、例2の問題の順番を入れ替えると変な答えになる。
{4,0,0,0,1}
{5,1,3,4,2}
{5,10,10,100,10}
Desired answer: 165 Your answer: 50 DOESN'T MATCH!!!!
コード見た感じ、より深い階層のものが最初の方にあるとダメですね。
これやるなら最初に階層（"階"ではなく、0からの道数）でソートしないと。
