【基礎アルゴリズム】雪かき車問題(BZOJ 1190)

問題L(1190):【基礎アルゴリズム】雪かき車問題
時間制限:1 Sec
メモリ制限:64 MB
コミット:132
解決:56
[コミット][ステータス][マイコミット]
タイトルの説明
大雪が都市全体を覆い、市役所は冬のサービス部にできるだけ早くいくつかの街(リストに記載されている)の積雪を除去して交通を回復するように要求した.都市全体は多くの交差点と街で構成されており、もちろん任意の2つの交差点は直接または間接的に連通している.リストは、これらの街の積雪が除去された後、任意の2つの交差点の間に通路が1つしかないように、最も少ない街を示しています.冬のサービス部門には雪かき車が1台と運転手が1人しかいません.この雪かき車の出発点はある交差点にあります.街に雪が積もっているかどうかにかかわらず、雪かき車は1メートル進むたびに燃料を1リットル消費します.冬季サービス部門は運転手にリスト上のすべての街の積雪を取り除く前提の下で、燃料の消費が最も少なく、シャベルが終わった後、車は任意の交差点に止まることができるように要求した.
入力
入力:最初の行は2つの整数N,Sを含む.(1 < =N < = 100000,1 < = S < =N).Nは交差点総数、Sは雪かき車が出発する交差点番号である.交差点の番号は1...N.次のN-1行動リストの街は、各行に3つのスペースで区切られた整数A,B,Cが含まれており、交差点Aから交差点Bまでの街を表し、Cはその街の長さである.単位はメートル、1<=C<=1000である.
しゅつりょく
出力:1行のみで、積雪をすべて取り除くために必要な最小限の燃料を表す整数が含まれています.
サンプル入力
Copy(コンソールにコピーして改行がない場合は、テキストエディタに貼り付けてからコピーできます)

5 1
1 2 8
1 3 10
3 4 10
4 5 7

サンプル出力

43

分析:まず、この図の2つの点の間には1つの道しかなく、nつの点、n-1つの辺なので、これは木です.次に、歩いた道を最短にし、最後にリーフノードまで行くたびにルートを返すため、所有権値の和を2に乗じてツリー上の最長ルートを減算すればよい.

#include
#include
#include
#include
#include
#include
using namespace std;
struct bian{
    int v,w,next;
}arr[400010];
int fir[200010],n,r,start,end,c,cnt,sum;
bool vis[200010];
int dfs(int x){
    vis[x]=1;
    int ans=0;
    for(int i=fir[x];i;i=arr[i].next){
        if(vis[arr[i].v])   continue ;
        int tmp=dfs(arr[i].v)+arr[i].w;
        ans=max(tmp,ans);
    }
    return ans;
}
int main(){
    scanf("%d %d",&n,&r);
    for(int i=1;i