ARC083 - omochan's diary

C
全通り試しましょう

D
とりあえず全部辺を張ってみて矛盾がないかワーシャルフロイド確かめましょう。矛盾があったら-1を返します。
もし矛盾がなかったら、頂点u,v,kについてdist(u,v)=dist(u,k)+dist(k,v)となっている辺(u,v)を取り除けます。

E
頂点を黒で塗ったら、その部分木の黒のコストはX[c]です。白のコストは小さければ小さいほどいいのでdp[v]として更新していけばよいです。

書くと簡単だけど、思いつくのはやっぱり時間がかかりますね…
典型を増やしていきたい。