题解：P14076 [GESP202509 六级] 货物运输

daizhuofan · 2025-09-29 20:42:51 · 题解

本人第一次写题解，希望大家见谅。

关于这道题没事么难点，以下是主要思路：

先算走完所有路程*2（回到原点，一去一回），再减去从原点出发最长单一路径。

code

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100010];//无向图。
vector<int> l[100010];//边权数组。
long long dfs1(int p, int fa){//从原点开始单一最长路径。
    long long x=0;
    for(int i=0;i<v[p].size();i++){
        if(v[p][i]==fa)  continue;
        x=max(x,dfs1(v[p][i],p)+l[p][i]);
    }
    return x;
}
long long dfs2(int p, int fa){//全路径。
    long long x=0;
    for(int i=0;i<v[p].size();i++){
        if(v[p][i]==fa)  continue;
        x+=dfs2(v[p][i],p)+l[p][i];
    }
    return x;
}
int main(){
    int n,x,y,z;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y>>z;
        v[x].push_back(y);//无向图vector
        v[y].push_back(x);//无向图vector
        l[x].push_back(z);//边权
        l[y].push_back(z);//边权
    }
    cout<<dfs2(1,0)*2-dfs1(1,0);//全路径*2-从原点开始单一最长路径。
    return 0;
}