华为笔试华为笔试题 0611

笔试时间：2025年6月11日暑期实习

第一题：货物运输

物流公司每天都要处理很多物流的运输工作，整个城市共有 ( N ) 个地点，共有 ( N - 1 ) 条公路，每 2 个地点之间都能通过公路连通。物流公司总部位于 1 号地点。

今天有一辆物流运输车共有 ( M ) 条物流运输任务，物流运输车每天的工作流程如下：

先要从总部出发去收取所有的寄件货物，收到所有货物后回到总部扫描货物，再从总部出发将货物送至所有的送件地址，送完后最终回到总部，算作完成了今天的运输工作。

请问该辆物流运输车今天最少行驶多少路程可以完成今天的运输工作，运输任务不分先后。

输入描述

对于每组数据，第一行有 2 个整数，依次为 ( N(3 \leq N \leq 10^5), M(1 \leq M \leq 10^5) )，表示有 ( N ) 个地点和 ( M ) 条物流任务，数字用空格分开。

接下来有 ( N - 1 ) 行，每行有 3 个整数，依次为 ( u(1 \leq u \leq N), v(1 \leq v \leq N), c(1 \leq c \leq 10^3) )，表示从 ( u ) 到 ( v ) 有一条公路，公路里程为 ( c )，输入保证所有地点连通。

接下来有 ( M ) 行，每行有 2 个整数，依次为 ( s(2 \leq s \leq N), t(2 \leq t \leq N, s \neq t) )，表示寄件任务从 ( s ) 寄到 ( t )。

输出描述

输出一个整数，表示该辆物流运输车最少行驶多少路程能够完成今天的运输工作。

样例输入

4 2

2 1 1

1 3 2

4 3 2

3 2

4 2

样例输出

10

解释：运输车从地点 1 开到地点 3 接收任务 1 物品，再开到地点 4 接收任务 2 物品，回到总部 1 扫描，扫描后将任务 1 和任务 2 的物品送到地点 2，最终回到总部 1，总共行驶里程 10。

参考题解

题目中的城市结构是一棵树（N个地点，N-1条公路，连通无环），总部位于1号地点。运输车需要访问所有寄件地点和所有送件地点，并且每次都是从总部出发再回到总部。收集阶段：运输车从总部出发，访问所有寄件地点，然后返回总部。最优路径是访问所有寄件地点所在的子树，每条边只需走一次。配送阶段：运输车从总部出发，访问所有送件地点，然后返回总部。同样，最优路径是访问所有送件地点所在的子树，每条边只需走一次。总路程：收集阶段和配送阶段的总路程是两倍的子树路径长度之和（因为每次都需要往返）。算法选择：使用深度优先搜索（DFS）来遍历树，标记哪些子树包含寄件地点或送件地点。对于每条边，如果其子树中包含寄件地点或送件地点，则这条边需要被计入总路程。实现步骤：构建树的邻接表表示。标记所有寄件地点和送件地点。使用DFS计算包含寄件地点的子树的总边权和（source_path_len）。使用DFS计算包含送件地点的子树的总边权和（dest_path_len）。总路程为 2 * (source_path_len + dest_path_len)。

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
vector<vector<pair<int,int>>> adj;
vector<bool> is_source_node, is_dest_node;
ll source_path_len = 0, dest_path_len = 0;

bool dfs_source(int u, int p) {
    bool has = is_source_node[u];
    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        if (dfs_source(v, u)) {
            source_path_len += w;
            has = true;
        }
    }
    return has;
}

bool dfs_dest(int u, int p) {
    bool has = is_dest_node[u];
    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        if (dfs_dest(v, u)) {
            dest_path_len += w;
            has = true;
        }
    }
    return has;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    adj.assign(n+1, {});
    for (int i = 0; i < n-1; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }
    is_source_node.assign(n+1, false);
    is_dest_node.assign(n+1, false);
    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        is_source_node[s] = true;
        is_dest_node[t] = true;
    }

    dfs_source(1, 0);
    dfs_dest(1, 0);

    ll total_distance = (source_path_len + dest_path_len) * 2;
    cout << total_distance << "\n";
    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static List<List<Edge>> adj;
    static boolean[] isSource, isDest;
    static long sourcePathLen = 0, destPathLen = 0;

    static class Edge {
        int to, w;
        Edge(int to, int w) { this.to = to; this.w = w; }
    }

    static boolean dfsSource(int u, int p) {
        boolean has = isSource[u];
        for (Edge e : adj.get(u)) {
            int v = e.to, w = e.w;
            if (v == p) continue;
            if (dfsSource(v, u)) {
                sourcePathLen += w;
                has = true;
            }
        }
        return has;
    }

    static boolean dfsDest(int u, int p) {
        boolean has = isDest[u];
        for (Edge e : adj.get(u)) {
            int v = e.to, w = e.w;
            if (v == p) continue;
            if (dfsDest(v, u)) {
                destPathLen += w;
                has = true;
            }
        }
        return has;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>(n+1);
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj.get(u).add(new Edge(v, c));
            adj.get(v).add(new Edge(u, c));
        }

        isSource = new boolean[n+1];
        isDest   = new boolean[n+1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            isSource[s] = true;
            isDest[t]   = true;
        }

        dfsSource(1, 0);
        dfsDest(1, 0);

        long total = (sourcePathLen + destPathLen) * 2;
        System.out.println(total);
    }
}

Python：

import sys

sys.setrecursionlimit(200005)

source_path_len = 0
dest_path_len = 0

def dfs_source(u, p, adj, is_source_node):
    global source_path_len
    has_source_in_subtree = is_source_node[u]
    if u in adj:
        for v, weight in adj[u]:
            if v == p:
                continue
            if dfs_source(v, u, adj, is_source_node):
                source_path_len += weight
                has_source_in_subtree = True
    return has_source_in_subtree

def dfs_dest(u, p, adj, is_dest_node):
    global dest_path_len
    has_dest_in_subtree = is_dest_node[u]
    if u in adj:
        for v, weight in adj[u]:
            if v == p:
                continue
            if dfs_dest(v, u, adj, is_dest_node):
                dest_path_len += weight
                has_dest_in_subtree = True
    return has_dest_in_subtree

def solve():
    n, m = map(int, sys.stdin.readline().split())
    adj = {}
    for _ in range(n - 1):
        u, v, c = map(int, sys.stdin.readline().split())
        if u not in adj: adj[u] = []
        if v not in adj: adj[v] = []
        adj[u].append((v, c))
        adj[v].append((u, c))
    is_source_node = [False] * (n + 1)
    is_dest_node = [False] * (n + 1)
    for _ in range(m):
        s, t = map(int, sys.stdin.readline().split())
        is_source_node[s] = True
        is_dest_node[t] = True
    dfs_source(1, 0, adj, is_source_node)
    dfs_dest(1, 0, adj, is_dest_node)
    total_distance = (source_path_len + dest_path_len) * 2
    print(total_distance)

if __name__ == "__main__":
    solve()