简答题
偏难
#20025
货物运输
货物运输



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
int n;
vector<vector<pair<int, int>>> e;
long long total_sum, max_dist;
// u当前节点 fa父节点 d从起点1走到u的距离
void dfs(int u, int fa, long long d) {
max_dist = max(d, max_dist);
for (auto edge : e[u]) {
int v = edge.first;
int w = edge.second;
if (v != fa) {
dfs(v, u, d + w);
}
}
}
int main() {
scanf("%d", &n);
e.resize(n + 1);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
total_sum += w;
}
dfs(1, 0, 0);
// 总往返路程 - 最长单条路径(不用折返)
long long ans = total_sum * 2 - max_dist;
printf("%lld\n", ans);
return 0;
}</pre>
这道题暂未补解析。