AOJ : 0235 - サージェント・ライアン (Sergeant Rian)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0235&lang=jp
日本語の問題文なので, 説明は省略.

アルゴリズム

"ある島からある島への経路は１通りしかない" という記述から, 閉路がない木構造であることがわかります.
つまり, １の島を根とする木構造となります.

木構造の葉にあたる島にかかる橋は, その手前の島から爆破できるため, 絶対に渡らないことがわかります.
また, 必ず最後は, 葉の親となる島で終わることがわかります.
葉の親となる島はいくつか存在しますが, その中でも, 島１からの到達時間が一番長いところが最後に訪問する島となります.

結果, プログラムは, 次のように単純なものになります.

• 葉にあたる島以外の島へかかる橋の時間のコストを全て足し合わせて２倍 = sum
• 根（１の島）から葉の親までの到達時間の中で, 一番最大のものを sum から引くと, これが答え

プログラム

int n;
int t[22][22];

int solve(int idx){
  int res = 0;
  rep(i,n){
    if(t[idx][i] > 0){
      t[i][idx] = 0;
      res = max(res,t[idx][i]+solve(i));
    }
  }
  return res;
}

int main(void){
  while(cin>>n,n){
    memset(t,0,sizeof(t));

    int sum = 0;
    rep(i,n-1){
      int a,b,cost;
      cin>>a>>b>>cost;
      t[a-1][b-1] = t[b-1][a-1] = cost;
      sum += cost * 2;
    }

    rep(i,n){
      int cnt=0, idx;
      rep(j,n){
        if(t[i][j] > 0 || t[i][j] == -1){
          cnt++;
          idx = j;
        }
      }
      if(i != 0 && cnt == 1){
        sum -= 2 * t[i][idx];
        t[i][idx] = t[idx][i]= -1;
      }
    }

    cout<<sum-solve(0)<<endl;
  }

  return 0;
}