4731: 【GESP2509六级】货物运输

#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;
}

/*
 * 试题名称：货物运输
 * 题目大意：给定一棵n个结点的树，首都为1号结点。车队从首都出发，必须访问全部城市，可以重复走道路，最后不用返回首都。
 * 求走过道路的最小总长度。
 *
 * 算法思路：
 * 1. 遍历整棵树并且返回起点，每条边都要来回走两次，总代价 = 所有边权之和 * 2
 * 2. 不需要返回起点，可以选择距离首都最远的那条路径，不用折返回来，直接省去这一段返程
 * 3. 最终答案 = 全部边权总和 * 2 − 首都(1)出发能到达的最远距离
 *
 * 实现：使用BFS迭代遍历，避免递归DFS在n=1e5时栈溢出
 */
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 100005;

vector<pair<int, long long>> adj[MAXN]; // adj[ u ] 邻接表：(邻接点,边长度)
long long dist[MAXN];   // dist[x]：1号点到x点的距离

int main()
{
    int n;
    scanf("%d", &n);

    long long sum_edge = 0;
    // 读入n‑1条双向边
    for(int i = 1; i <= n - 1; ++i)
    {
        int u, v;
        long long l;
        scanf("%d %d %lld", &u, &v, &l);
        adj[ u ].emplace_back(v, l);
        adj[ v ].emplace_back(u, l);
        sum_edge += l;
    }

    // BFS求1到每个点距离
    queue<int> q;
    for(int i = 1; i <= n; i++) dist[i] = -1; //‑1标记未访问
    dist[1] = 0;
    q.push(1);

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto &edge : adj[ u ])
        {
            int v = edge.first;
            long long w = edge.second;
            if(dist[ v ] == -1)
            {
                dist[ v ] = dist[ u ] + w;
                q.push(v);
            }
        }
    }

    // 找1号点出发最远的距离
    long long max_dist = 0;
    for(int i = 1; i <= n; ++i)
    {
        max_dist = max(max_dist, dist[i]);
    }

    long long answer = sum_edge * 2 - max_dist;
    printf("%lld\n", answer);
    return 0;
}