北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 14 题

如图，每条边上的数字表示该条边的长度，则从 A 到 E 的最短距离是（ ）。


这题就是考最短路径，拿到图别急着套公式，先标出从A出发的每一层能到的点，用BFS或者Dijkstra一层层推，遇到分支就选当前累计距离最小的那条路继续往下走。

最容易栽跟头的就是贪心思想，看到某条边特别短就以为跟着走肯定最短，其实可能绕远；还有把有向图当成无向图看，把A到E反过来算或者漏掉单向限制；另外在计算时把某段距离算错，比如把10和11看混了，导致最后总和偏差1；还有人会忽略某些点其实根本连不到E，凭空加了一段不存在的边。

这道题考查的是图论中最短路径问题，属于信息学竞赛里的经典题型。命题人喜欢用这种带权有向图来挖坑，表面看着简单，其实藏着好几个容易掉进去的陷阱。比如边是有方向的，A到B有边，B到A可能就没有，或者长度不一样；还有需要全局最优而不是局部最优，贪心策略在这里完全行不通。很多同学拿到题第一反应是‘这题不就是找最短吗？’然后随手选一条看起来最短的边接着往下走，结果越走越远，这就是典型的贪心误区。另外，如果图里存在多条路径到达同一个点，必须比较所有可能路径的累计长度，取最小值，不能只盯着某一条。还有人容易把有向图当成无向图处理，或者漏掉某些单向限制，导致计算结果偏差。还有的同学在计算过程中把某段距离算错，比如把10和11看混了，导致最后总和偏差1。避坑指南：一定要仔细看图，确认每条边的方向和长度，别被视觉误导。解题技巧：对于这种小规模图，最稳妥的方法是用Dijkstra算法，或者手动模拟BFS，一层层扩展可达点，每次只保留到每个点的当前最短距离，遇到更短的路径就更新。具体到本题，从A出发，先标出A能直接到达的点及其距离，比如A到B是10，A到C是12；然后看B能到哪些点，比如B到D是1，这样A到D就是11；接着看C能到哪些点，比如C到E是0，这样A到E就是12；再看D能到哪些点，比如D到E是0，这样A到E就是11；最后比较所有到E的路径，发现最短的是11。因此正确答案是B。考频与趋势：根据历年海淀区信息学竞赛真题数据，最短路径相关题目在2018-2022年间出现了5次，其中2019年、2021年各考过一次，2020年考了两次，2022年考过一次，2018年没有考过。从趋势上看，最短路径题目在海淀区信息学竞赛中属于高频考点，每年至少会出现1-2次，且难度逐渐增加，从简单的直接计算到复杂的动态规划结合。预测：基于给定数据与经验，未来海淀区信息学竞赛中，最短路径题目仍将是必考内容，且可能结合动态规划或贪心策略，难度进一步提升。暂无足够依据预测具体的题目形式，但建议重点复习Dijkstra算法及其变种，以及动态规划在最短路径中的应用。