在线机考|2025年华为暑期实习春招秋招编程题（最新）——第1题_物流运输

题目内容

输入输出描述

样例

输入

4 2 
2 1 1
1 3 2
4 3 2
3 2 
4 2

输出

10

题目解析

代码实现

C++

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const int MAXN = 100000 + 5;int N, M;
vector<pair<int,int>> adj[MAXN]; // 邻接表： (邻居, 权重)
int fa[MAXN];                    // 父节点
int order[MAXN], ord_cnt;        // BFS/DFS 拓扑序
ll cntS[MAXN], cntT[MAXN];       // 子树内寄件计数、送件计数int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N >> M;for (int i = 1; i <= N; i++) {adj[i].clear();cntS[i] = cntT[i] = 0;}// 读入 N-1 条边for (int i = 0; i < N-1; i++) {int u, v, c;cin >> u >> v >> c;adj[u].push_back({v, c});adj[v].push_back({u, c});}// 以 1 为根，BFS 建立父节点和拓扑序queue<int> q;vector<bool> vis(N+1, false);q.push(1);vis[1] = true;ord_cnt = 0;while (!q.empty()) {int u = q.front(); q.pop();order[ord_cnt++] = u;for (auto [v, w] : adj[u]) {if (!vis[v]) {vis[v] = true;fa[v] = u;q.push(v);}}}// 读任务，标记寄件点和送件点for (int i = 0; i < M; i++) {int s, t;cin >> s >> t;cntS[s]++;cntT[t]++;}// 后序汇总子树计数（倒序遍历拓扑序）for (int i = ord_cnt - 1; i > 0; i--) {int u = order[i];cntS[fa[u]] += cntS[u];cntT[fa[u]] += cntT[u];}// 累加答案ll sumS = 0, sumT = 0;for (int u = 2; u <= N; u++) {int p = fa[u];// 找到父子边权int w = 0;for (auto [v, wt] : adj[u]) {if (v == p) { w = wt; break; }}if (cntS[u] > 0) sumS += w;if (cntT[u] > 0) sumT += w;}// 总路程ll ans = 2 * (sumS + sumT);cout << ans << "\n";return 0;
}

Python

from collections import deque
import sys
input = sys.stdin.readlinedef main():N, M = map(int, input().split())adj = [[] for _ in range(N+1)]for _ in range(N-1):u, v, c = map(int, input().split())adj[u].append((v, c))adj[v].append((u, c))# BFS 建立父节点与拓扑序fa = [0] * (N+1)order = []q = deque([1])visited = [False] * (N+1)visited[1] = Truewhile q:u = q.popleft()order.append(u)for v, _ in adj[u]:if not visited[v]:visited[v] = Truefa[v] = uq.append(v)# 子树计数cntS = [0] * (N+1)cntT = [0] * (N+1)for _ in range(M):s, t = map(int, input().split())cntS[s] += 1cntT[t] += 1# 后序汇总for u in reversed(order[1:]):  # 跳过根 1cntS[fa[u]] += cntS[u]cntT[fa[u]] += cntT[u]sumS = sumT = 0# 累加各边权for u in range(2, N+1):p = fa[u]# 找到边权for v, w in adj[u]:if v == p:if cntS[u] > 0:sumS += wif cntT[u] > 0:sumT += wbreakans = 2 * (sumS + sumT)print(ans)if __name__ == "__main__":main()

Java

import java.io.*;
import java.util.*;public class Main {static int N, M;static List<int[]>[] adj;static int[] fa, order;static long[] cntS, cntT;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 List[N+1];for (int i = 1; i <= N; i++) {adj[i] = 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[u].add(new int[]{v, c});adj[v].add(new int[]{u, c});}// BFS 建树fa = new int[N+1];order = new int[N];boolean[] vis = new boolean[N+1];Queue<Integer> q = new ArrayDeque<>();q.offer(1);vis[1] = true;int idx = 0;while (!q.isEmpty()) {int u = q.poll();order[idx++] = u;for (int[] e : adj[u]) {int v = e[0];if (!vis[v]) {vis[v] = true;fa[v] = u;q.offer(v);}}}cntS = new long[N+1];cntT = new long[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());cntS[s]++;cntT[t]++;}// 后序汇总for (int i = N-1; i > 0; i--) {int u = order[i];cntS[fa[u]] += cntS[u];cntT[fa[u]] += cntT[u];}long sumS = 0, sumT = 0;// 累加边权for (int u = 2; u <= N; u++) {int p = fa[u];int w = 0;for (int[] e : adj[u]) {if (e[0] == p) {w = e[1];break;}}if (cntS[u] > 0) sumS += w;if (cntT[u] > 0) sumT += w;}long ans = 2 * (sumS + sumT);System.out.println(ans);}
}