华为 OD 机试：快递站点投递路径分析与解法

快递投放问题解析

在华为 OD 机试的双机位 C 卷中，这类图论结合业务场景的题目非常典型。核心在于如何根据给定的道路网络和检查站限制，判断包裹能否从起点到达终点。

题目理解

我们需要处理 N 个站点和 M 个包裹的投递任务。站点之间通过道路连接，但某些路段设有检查站，会拦截特定类型的货物。我们的目标是找出所有无法完成投递的包裹编号。

输入输出规范

• 输入：第一行包含两个整数 M 和 N（M 为包裹数，N 为道路数）。后续行描述包裹信息和道路连接。
• 输出：无法送达的包裹列表，按升序排列；若全部可达则输出 none。

注意：实际机考中，输入格式可能因具体年份略有差异，建议以现场示例为准，重点掌握图遍历逻辑。

解题思路

这道题本质上是一个有向图的连通性问题。我们可以将站点视为节点，道路视为边。对于每个包裹，我们需要判断其起点到终点是否存在一条不被检查站阻断的路径。

算法选择

由于需要多次查询不同包裹的可达性，且数据规模通常不大（N, M <= 100），使用 BFS（广度优先搜索） 或 DFS（深度优先搜索） 即可高效解决。每次针对一个包裹进行一次图遍历，复杂度约为 O(M * (V + E))，完全在可接受范围内。

关键点

1. 图构建：需要动态维护站点间的邻接关系。如果存在双向道路，需添加两条边。
2. 检查站逻辑：题目中提到'检查站禁止通行'，这通常意味着某些边带有属性（如禁止类型）。在代码实现时，可以将边标记为允许或禁止，遍历时跳过禁止边。
3. 结果排序：输出前务必对无法送达的包裹 ID 进行排序，这是容易丢分的细节。

代码实现

下面给出基于 Java 的实现方案。为了保持代码清晰，我们采用邻接表存储图结构。

import java.util.*;

public class Main {
    // 定义边的内部类，记录目标站点和是否被检查站拦截
    static class Edge {
        int to;
        boolean blocked;
        public Edge(int to, boolean blocked) {
            this.to = to;
            this.blocked = blocked;
        }
    }

    public static void main(String[] args) {
        Scanner scanner   (System.in);
         (!scanner.hasNextInt()) ;
        
           scanner.nextInt(); 
           scanner.nextInt(); 
        
        
        List<Package> packages =  <>();
         (   ; i < m; i++) {
               scanner.next();
               scanner.next();
               scanner.next();
            packages.add( (pkgName, startNode, endNode));
        }
        
        
        Map<String, Integer> nodeMap =  <>();
        List<List<Edge>> graph =  <>();
        
        
        
         (   ; i < n; i++) {
               scanner.next();
               scanner.next();
               scanner.nextBoolean(); 
            
             (!nodeMap.containsKey(u)) nodeMap.put(u, nodeMap.size());
             (!nodeMap.containsKey(v)) nodeMap.put(v, nodeMap.size());
            
               nodeMap.get(u);
               nodeMap.get(v);
            
             (graph.size() <= Math.max(uIdx, vIdx)) graph.add( <>());
            
            graph.get(uIdx).add( (vIdx, isBlocked));
            graph.get(vIdx).add( (uIdx, isBlocked)); 
        }
        
        List<String> failedPackages =  <>();
        
        
         (Package pkg : packages) {
             (!nodeMap.containsKey(pkg.start) || !nodeMap.containsKey(pkg.end)) {
                failedPackages.add(pkg.name);
                ;
            }
            
             (!bfs(nodeMap.get(pkg.start), nodeMap.get(pkg.end), graph)) {
                failedPackages.add(pkg.name);
            }
        }
        
        
        Collections.sort(failedPackages);
         (failedPackages.isEmpty()) {
            System.out.println();
        }  {
                ();
             (   ; i < failedPackages.size(); i++) {
                sb.append(failedPackages.get(i));
                 (i < failedPackages.size() - ) sb.append();
            }
            System.out.println(sb.toString());
        }
    }
    
    
        {
         (start == end)  ;
        Queue<Integer> queue =  <>();
        Set<Integer> visited =  <>();
        
        queue.offer(start);
        visited.add(start);
        
         (!queue.isEmpty()) {
               queue.poll();
             (Edge edge : graph.get(curr)) {
                 (!edge.blocked && !visited.contains(edge.to)) {
                     (edge.to == end)  ;
                    visited.add(edge.to);
                    queue.offer(edge.to);
                }
            }
        }
         ;
    }
    
       {
        String name, start, end;
          {
            .name = name;
            .start = start;
            .end = end;
        }
    }
}