题目背景对应的选择、判断题试题 - GESP 202509 C 六级 - 洛谷有题题目描述A 国有 n 座城市依次以 1,2,…,n 编号其中 1 号城市为首都。这 n 座城市由 n−1 条双向道路连接第 i 条道路1≤in连接编号为 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≤1051≤ui​,vi​≤n1≤li​≤109。代码实现#include iostream #include vector #include queue using namespace std; typedef long long ll; struct Edge { int to; ll len; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorEdge g(n1); ll sum_all 0; for(int i 1; i n-1; i) { int u, v; ll l; cin u v l; g[u].push_back({v, l}); g[v].push_back({u, l}); sum_all l; } vectorll dist(n1, 0); vectorbool vis(n1, false); queueint q; q.push(1); vis[1] true; ll maxd 0; while(!q.empty()) { int u q.front(); q.pop(); for(auto e : g[u]) { int v e.to; ll w e.len; if(!vis[v]) { vis[v] true; dist[v] dist[u] w; if(dist[v] maxd) maxd dist[v]; q.push(v); } } } ll ans 2 * sum_all - maxd; cout ans endl; return 0; }