Problem 0235 : Sergeant Rian

問題概要

日本語なので本文参照
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0235&lang=jp）

解法

グラフをノード1を根とする木と考える。
dp[i]を、i以下のサブツリーのエッジを全て爆破してiに戻ってくるのにかかる最小の時間とする。
また、dp2[i]を、i以下のサブツリーのエッジを全て爆破するのにかかる最小の時間とする。

子をもたないノードは訪れる必要がないので、
dp[i]はΣ{d[i][j]*2+dp[j]|jはiの子のうち子をもつノード}となる。

dp2[i]は、dp[i]のうち、どこか一つのノードへ行ったきり戻ってこない（他のノードからは爆破後戻ってくる）ときのコストである。
よってdp2[i]はmin{dp[i]-(jに行かなかったことにする)+dp2[j]|jはiの子のうち子を持つノード}
と書ける。
以上の漸化式でDPすればよい。

ソースコード

const int inf=1<<29;
int n,dp[100],dp2[200];
vector<vector<pair<int,int> > > e;

void rec(int c,int p){
	fr(i,e[c])if(i->first!=p&&e[i->first].size()>1){
		rec(i->first,c);
		dp[c]+=2*i->second+dp[i->first];
	}
	dp2[c]=dp[c];
	fr(i,e[c])if(i->first!=p&&e[i->first].size()>1){
		dp2[c]=min(dp2[c],dp[c]-i->second-dp[i->first]+dp2[i->first]);
	}
}
int main(){
	while(cin>>n,n){
		e.clear(); e.resize(n);
		rep(i,n-1){
			int a,b,t; cin>>a>>b>>t;
			a--; b--;
			e[a].pb(mp(b,t)); e[b].pb(mp(a,t));
		}
		rep(i,n)dp[i]=0,dp2[i]=inf;
		rec(0,-1);
		cout<<dp2[0]<<endl;
	}
	return 0;
}