NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 21 题

有 $6$ 个城市，任何两个城市之间都有一条道路连接，$6$ 个城市两两之间的距离如下表所示，则城市 $1$ 到城市 $6$ 的最短距离为_____________。

	城市1	城市2	城市3	城市4	城市5	城市6
城市1	0	2	3	1	12	15
城市2	2	0	2	5	3	12
城市3	3	2	0	3	6	5
城市4	1	5	3	0	7	9
城市5	12	3	6	7	0	2
城市6	15	12	5	9	2	0

这题本质是求有向完全图里两点间最短路径，但陷阱在于它不是让你写 Dijkstra，而是让你像看地图一样，先找离起点最近的邻居，再顺着邻居找下一个更近的点，一层层往外推。

最容易掉进两个坑：一是机械套用 Dijkstra 公式，把中间节点的距离加错，比如 1→2→3→6 算成 2+2+5=9，其实 1→2→5→6 才是 7；二是被表里数字大吓到，以为只能走一步，忘了可以绕路，比如 1→4→3→5→6 虽然总长 12，但中间某些子路径可能更短，只是整体不是最优。

这道题考查的是最短路径思想，但命题人特意把图设计成完全图，让你不能只盯着直接相连的边，得学会‘跳一跳’。核心概念很简单：从起点出发，先找到离它最近的那个城市，再从那个城市找离它最近的下个城市，一层层往外推，直到摸到终点。命题人挖坑的地方往往在中间那几跳——你以为 1→2→3→6 是顺理成章的，其实 2 到 5 比 2 到 3 更近，所以 1→2→5→6 才是真正的最短路线。拿到题先想什么？先列个表格，把每个城市到起点的距离写下来，然后按从小到大排序，一个个去验证能不能通过已经确定的最短路径再连一条边，得到新的更短路径。具体怎么算？从城市 1 出发，直接相连的距离分别是：到 4 是 1，到 2 是 2，到 3 是 3，到 5 是 12，到 6 是 15。显然最近的是 4，但 4 到 6 是 9，加起来 1+9=10，还没到 7。接下来看 2，2 到 5 是 3，2 到 3 是 2，2 到 6 是 12。这时候别急着加，先想想：1→2 已经确定了最短是 2，那从 2 出发能不能找到一条到 6 的路，比 10 更小？2→5→6 就是 2+3+2=7，比 10 小多了！再回头看看 3，1→3 是 3，3→6 是 5，加起来 8，还是比 7 大。所以最短路径就是 1→2→5→6，总长 7。避坑的关键是别被数字大小误导，比如有人会觉得 1→4→3→6 是 1+3+5=9，其实 4→3 是 3，3→6 是 5，加起来是 9，但 1→2→5→6 才是 7。考频与趋势方面，最短路径在近五年爆发式增长：2024 年考了 6 题，2025 年考了 7 题，2026 年也考了 7 题，说明命题人越来越喜欢用这种‘看似简单实则需细心’的题目来区分学生。预测的话，未来几年大概率还会继续考这类最短路径，而且可能会结合更复杂的图结构，比如带权边、动态更新或者多起点多终点的情况，但核心思路不变：先找最近邻居，再层层推进。