A23778. 货物运输A 国有n座城市，依次以1,2,...,n编号，其中 1 号城市为首都。这n座城市由n - 1条双向道路连接，第i条道路(1≤i< n)连接编号为ui,vi的两座城市，道路长度为li。任意两座城市间均可通过双向道路到达。现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首…
填空题
困难
知识点
题目描述
货物运输
A 国有n座城市，依次以1,2,...,n编号，其中 1 号城市为首都。这n座城市由n - 1条双向道路连接，第i条道路(1≤i< n)连接编号为ui,vi的两座城市，道路长度为li。任意两座城市间均可通过双向道路到达。
现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。
输入格式
第一行，一个正整数n，表示 A 国的城市数量。
接下来n - 1行，每行三个整数ui,vi,li，表示一条双向道路连接编号为ui,vi的两座城市，道路长度为li。
输出格式
一行，一个整数，表示你设计的路线所经过的道路长度总和。
样例
输入样例 1
4
1 2 6
1 3 1
3 4 5输出样例 1
18输入样例 2
7
1 2 1
2 3 1
3 4 1
7 6 1
6 5 1
5 1 1输出样例 2
9数据范围
对于30% 的测试点，保证 1≤n≤8。
对于另外30% 的测试点，保证仅与一条双向道路连接的城市恰有两座。
对于所有测试点，保证 1≤n≤105 ，1≤ui,vi≤n ， 1≤li≤109。
参考答案
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<vector<pair<int, int>>> e;
long long s, mx;
void dfs(int u, int f, long long d) {
mx = max(d, mx);
for (auto p : e[u]) {
if (p.first != f) { dfs(p.first, u, d + p.second); }
}
}
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(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
s += w;
}
dfs(1, 0, 0);
printf("%lld\n", s * 2 - mx);
return 0;
}
上一题
下一题