[GESP2025 六级] 货物运输题解

看完后
点赞+加入团队

#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> a[100005];
queue<pair<long long,long long>> q;
int vis[100005];
long long ans,maxn;

void bfs()
{
    q.push({1,0});
    while (!q.empty())
    {
        long long u=q.front().first;
        long long l=q.front().second;
        q.pop();
        maxn=max(maxn,l);
        vis[u]=1;
        for (int i=0;i<a[u].size();i++)
        {
            long long u1=a[u][i].first;
            if (vis[u1]) continue;
            long long l1=a[u][i].second;
            l1+=l;
            q.push({u1,l1});
        }
    }
}

int main()
{
	int n;
    cin >> n;
    for (int i=1;i<n;i++)
    {
        int u,v,l;
        cin >> u >> v >> l;
        a[u].push_back({v,l});
        a[v].push_back({u,l});
        ans+=l*2;
    }
    bfs();
    cout << ans-maxn;
	return 0;
}