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

通过题意，

这 $n$ 座城市由 $n-1$ 条双向道路连接。

我们可以知道，这是一棵树，~~CCF不会给我们弄一个非连通图~~。如果每次运送完货物都需要回首都的话，那么最后的路程一定是所有路径的长度和的两倍。但是题目说了，最后不用返回首都，那么让我们来观察一下，最短路程是什么。

CPP

画的有点丑，请谅解。

上面的图上每条边左边或右边的数字代表边的长度，这个图上离首都最远的叶子节点是节点

4

，他与首都的距离是

1+7=8

，所以我们要用所以边的长度和两倍减去图上离首都最远的叶子节点与首都的距离，才能得到最短路程，对于上面的图，答案是

9

。

代码：

CPP

#include <iostream>
#include <vector>
using namespace std;
vector<int> a[100001];
vector<long long> b[100001];
long long r[100001],ans;
bool vis[100001];
void f(int x)
{
    if(a[x].empty()) return;
    for(int i=0;i<=a[x].size()-1;++i)
    {
        if(vis[a[x][i]]==1) continue;
        vis[a[x][i]]=1;
        r[a[x][i]]=r[x]+b[x][i];
        ans=max(ans,r[a[x][i]]);
        f(a[x][i]);
    }
}
int main()
{
    int n,u,v;
    long long l,cnt=0;
    cin>>n;
    for(int i=1;i<=n-1;++i)
    {
        cin>>u>>v>>l;
        a[u].push_back(v);
        a[v].push_back(u);
        b[u].push_back(l);
        b[v].push_back(l);
        cnt+=l;
    }
    vis[1]=1;
    f(1);
    cout<<cnt+cnt-ans;
    return 0;
}

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

文章操作

代码：

相关推荐

评论

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