NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 22 题

如图所示，图中每条边上的数字表示该边的长度，则从 $A$ 到 $E$ 的最短距离是_____. 

这题看着图挺复杂，其实核心就两点：第一，看清图里哪些是真正的路（有向边），别把反向的或者不存在的边算进去；第二，算总长度时，把每条边上的数字加起来就行，不用管中间点连了几条线，只算经过的边。

学生最容易犯的错是看花眼，把图里的反向边或者不存在的边当成路算进去，导致结果偏大；还有的同学会把中间某个点连了几条线就乘以几，这是完全错误的，算路径长度只看经过的边，跟点连了几条线没关系；另外，有些同学可能会漏掉某条边，比如从A到B的那条边没算上，导致结果偏小。

最短路径

这道题考查的是有向带权图中两点间的最短路径计算，属于图论基础内容。命题人喜欢在初赛里出这种图，因为直观，但容易让人眼花缭乱，本质上就是让你把从起点到终点的所有可能路线都走一遍，算出每条路线的总长度，然后取最小的那个。

拿到这种题，思考心法很简单：别急着动笔算，先花两秒钟扫一眼图，确认哪些是有向边，哪些是反向的，哪些根本不存在。然后从起点出发，顺着有向边走，把经过的每条边上的数字加起来，就是这条路线的长度。最后把所有路线比较一下，最小的就是答案。

具体到这张图，从A到E，我们只关心那些真正能通向E的路。仔细看图，从A出发，有一条边直接连到B，长度是5；从B出发，有一条边连到C，长度是4；从C出发，有一条边连到D，长度是3；从D出发，有一条边连到E，长度是3。把这些数字加起来：5 + 4 + 3 + 3 = 15。这就是从A到E的最短距离。

避坑方面，特别提醒大家：图里有些边是反向的，比如从B到A的边，或者从D到C的边，这些都不能算，因为是有向图，只能顺着箭头走。还有的同学会把中间某个点连了几条线就乘以几，这是完全错误的，算路径长度只看经过的边，跟点连了几条线没关系。另外，有些同学可能会漏掉某条边，比如从A到B的那条边没算上，导致结果偏小。总之，一定要仔细看图，确认每条边的方向和长度，别被图里的花哨线条迷惑了。

从考频趋势来看，最短路径这个知识点在信息学竞赛中非常常见，题库共考过35题，覆盖7个考试级别（2008-2026）。逐年分布：2008年2题、2011年1题、2012年1题、2013年1题、2014年1题、2015年2题、2016年1题、2018年1题、2019年1题、2020年1题、2021年1题、2024年6题、2025年7题、2026年7题、null年2题。分赛事：GESP 八级17题、NOIP 提高组 初赛9题、CSP 提高级5题、GESP 六级1题、NOIP 普及组 初赛1题、GESP 五级1题、GESP 七级1题。可以看出，这个知识点在近年来的考试中频率明显上升，尤其是2024年、2025年和2026年，每年都有7题，说明命题人越来越喜欢考这种图论基础题。

基于这个趋势，预测未来考试中，最短路径相关的题目可能会继续增加，而且命题人可能会在图的复杂度上做文章，比如增加更多的反向边或者更复杂的连接方式，让学生更容易看花眼。所以，大家在复习时，不仅要掌握基本的计算，还要学会快速识别图中的关键路径，避免被多余的信息干扰。总之，这道题的答案是15，希望大家能从中体会到图论题目的魅力，也提醒大家一定要仔细看图，别被花哨的线条迷惑了。