NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 22 题

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

拿到这张图别急着算，先圈出城市1能直接连到的点，把每条路标上权值，再用Dijkstra或手动枚举所有从1到6的路径，挑出最小的那条。

学生最容易犯两个错：一是把‘两两相连’误读成‘只有相邻编号的城市有路’，于是漏掉1→3→6这种跨编号的路径，导致算出更大的距离；二是加法算错，比如把1→3→6当成1+6=7却忘了中间还有边；三是看到表里数字大就以为是最短路径，其实最短路径往往由几条中等长度的边拼成，反而比单条长边还短。

考点与命题视角

这道题考的是最短路径（Dijkstra或枚举所有路径）。命题人喜欢把数据放在一张表里，让你自己找路径，而不是直接给算法框架。坑点在于：表里只给了6个城市两两之间的距离，没说只能走相邻编号的边，所以1→3→6这种“跳号”路径是合法的，但很多学生会因为惯性只考虑1→2→3→4→5→6，从而漏掉更短的路径。

概念：最短路径是人话

最短路径，就是从起点到终点，把所有经过的边的权值加起来，结果最小的那条路。Dijkstra算法就是反复找“当前未访问点里离起点最近的”，然后把它连到的点更新距离，直到终点被访问。