Submission

PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

Score: 100

User: Monasm

Problemset: Sirabyrinth 6

Language: cpp

Time: 0.021 second

Submitted On: 2025-02-09 22:50:27

#include <bits/stdc++.h>

#define pii pair<int,int>
#define int long long int
using namespace std;

int32_t main(){
    int n,k,ans=0,m=-1e18;cin>>n>>k;
    vector<pii> adj[n];
    vector<int> dist(n,1e18);
    for(int i=0;i<n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        ans+=w;
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,k});
    dist[k] = 0;
    while(!pq.empty()){
        int d = pq.top().first,u = pq.top().second;
        pq.pop();
        for(auto i:adj[u]){
            int v = i.first,w = i.second;
            if(dist[v]>w+d){
                dist[v]=w+d;
                pq.push({w+d,v});
            }
        }
    }
    for(int i=0;i<n;i++){
        m = max(m,dist[i]);
    }
    cout<<(ans*2)-m;
}