AOJ -0235 Sergent Rian

問題文:Sergeant Rian | Aizu Online Judge
すべての橋を爆破する最短コストは、最もコストが掛かる島(葉ではなく、1から到達するまでに最もコストがかかる島)を爆破する順番を最後にすれば良い。
サンプルを最短コストになるように鉛筆でなぞると、最もコストが掛かる島に辿り着くまでの橋以外は二度通ることになります。
したがって解法は

すべての橋を爆破するコスト*2-最長のコスト

となります。

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
#define int ll
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
class edge{
public:
    int to;
    int cost;
    void Init(){to=0; cost=0;}
    edge(int t, int c):to(t), cost(c){};
    
};
vi d(100,INF);
vector<edge>Edge[100];
void dijkstra(){
    d[1]=0;
    priority_queue<pii,vector<pii>,greater<pii> >que;
    que.push(pii(0,1));
    while(!que.empty()){
        pii now=que.top(); que.pop();
        int to_v=now.second;
        if(d[to_v]<now.first)continue;
        rep(i,Edge[to_v].size()){
            edge e=Edge[to_v][i];
            if(d[e.to]>d[to_v]+e.cost){
                d[e.to]=d[to_v]+e.cost;
                que.push(pii(d[e.to],e.to));
            }
        }
    }
}
signed main(){
    int n;
    while(cin>>n,n){
        vector<pair<pii,int>>data;
        rep(i,100)Edge[i].clear();
        rep(i,n-1){
            int from,to,cost;
            cin>>from>>to>>cost;
            Edge[from].push_back(edge(to,cost));
            Edge[to].push_back(edge(from,cost));
            data.push_back(make_pair(pii(from,to),cost));
        }
        int sum=0;
        rep(i,n+1)d[i]=INF;
        dijkstra();
        int maxi=0;
        for(int i=0; i<data.size();i++){
            if(data[i].first.first==1){
                if(Edge[data[i].first.second].size()==1)continue;
            }else if(data[i].first.second==1){
                if(Edge[data[i].first.first].size()==1)continue;
            }else if(Edge[data[i].first.first].size()==1 || Edge[data[i].first.second].size()==1)
                continue;
            sum+=data[i].second;
        }
        sum*=2;
        for(int i=1; i<=n;i++){
            if(i==1)continue;
            if(Edge[i].size()==1)continue;
            cmax(maxi, d[i]);
        }
        cout<<sum-maxi<<endl;
    }
}