P14076 [GESP202509 六级] 货物运输

前言

应该有人会跟我一样，卡了十几分钟的 \(vector<pair<int, int>>\) 的用法吧。

Solution

首先，我们应该知道，如果车队最后要返回根节点，那么\(ans\) 就是所有路径之和 * 2。但是这题说车队可以不返回根节点，那么贪心一下，以离根节点路径最长的叶子结点为终点。
（温馨提示：不开 \(long long\) 见祖宗）。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> v[100010];
int n, ans, maxn = -1e9;
void dfs(int now, int fa, int sum){for(auto i : v[now])if(i.first != fa)dfs(i.first, now, sum + i.second);maxn = max(maxn, sum);
}
signed main(){cin >> n;for(int i = 1; i < n; i++){int u, m, l;cin >> u >> m >> l;v[u].push_back(make_pair(m, l));v[m].push_back(make_pair(u, l));ans += l * 2;}dfs(1, -1, 0);cout << ans - maxn;
}

\(vector<pair<int, int>>\)用法

为了让更多的人不被卡住，我就稍讲一下。
首先，创立是很简单的，应该不用说。（不会这题别做了）。
其次，该如何询问呢？
我个人认为用 for 循环较好，模版代码：

for(auto i : v)//这里的v可以改成你的vector变量名//然后这里就可以用i来访问first和second啦！

注意，这里千万不能用 \(v[i].first\) 和 \(v[i].second\) 哦！（除非你用迭代器）
另外，加入数据时push_back也可以换成 emplace_back， 后者不用敲make_pair哦！